2.1. 线性表
2.1.1. 什么是线性表
线性表是由同类型的数据元素够坦诚有序序列的线性结构。
# 抽象结构描述
类型名称: List
数据对象集: 线性表是n个元素构成的有序序列(a1,a2,....an)
操作集:
List MakeEmpty(): 初始化一个空线性表。
ElementType FindKth(int K ,List L): 根据位序返回对应元素。
int Find(ElementType X,List L): 查找X第一次出现的位序号。
void Insert(ElementType X,int i,List L): 在位序前插入一个元素。
void Delete(int i ,List L): 删除指定位序的元素。
int Length(List L): 返回线性表L的长度n。
2.1.2. 线性表连续具体实现
1#include <stdio.h>
2#include <stdlib.h>
3
4#define MAXSIZE 5
5#define ElementType int
6
7typedef struct LNode *List;
8struct LNode {
9 ElementType Data[MAXSIZE];
10 int Len;
11};
12
13List MakeEmpty() {
14 List ptrl;
15 ptrl = (List) malloc(sizeof(struct LNode));
16 ptrl->Len = 0;
17 return ptrl;
18}
19
20
21int Find(ElementType x, List ptrl) {
22 int i = 0;
23 while (i < ptrl->Len && ptrl->Data[i] != x) {
24 i++;
25 }
26 if (i >= ptrl->Len ) {
27 return -1;
28 }
29 return i;
30}
31
32void Insert( ElementType x, int i, List ptrl ) {
33
34 if (ptrl->Len >=MAXSIZE){
35 printf("表满了,不能再插入了。\n") ;
36 return ;
37 }
38 if (i <0 || i >ptrl->Len){
39 printf("位置不合法\n");
40 return ;
41 }
42 int j =0 ;
43 for (j=ptrl->Len-1; j>=i ;j--){
44 ptrl->Data[j+1] = ptrl->Data[j] ;
45 }
46 ptrl->Data[i] = x ;
47 ptrl->Len +=1;
48}
49void Delete(int i , List ptrl){
50 if (i >=ptrl->Len || i<0) {
51 printf("删除位置不合适\n");
52 return;
53 }
54
55 int j=0;
56 for (j=i; j<ptrl->Len-1 ;j++){
57 ptrl->Data[j] = ptrl->Data[j+1];
58 }
59 ptrl->Len -=1;
60 return ;
61}
62
63
64void Print(List ptrl) {
65 int i;
66 for (i = 0; i < ptrl->Len; i++) {
67 printf("%d ", ptrl->Data[i]);
68 }
69 printf("\n");
70}
71
72
73int main() {
74 List ptrl;
75 int index ;
76
77 ptrl = MakeEmpty();
78 Insert(1,0,ptrl);
79 Insert(2,1,ptrl);
80 Insert(3,2,ptrl);
81 Insert(4,3,ptrl);
82 //Insert(5,4,ptrl);
83 // Insert(6,5,ptrl);
84 //Insert(6,7,ptrl);
85
86 index = Find(3,ptrl);
87 printf("find %d in list index=%d\n ",3, index);
88 Print(ptrl);
89
90 Delete(5,ptrl);
91 Print(ptrl);
92 Delete(0,ptrl);
93 Print(ptrl);
94
95 return 0;
96}
97
2.1.3. 线性表链式具体实现
1#include <stdio.h>
2#include <stdlib.h>
3
4#define ElementType int
5
6typedef struct LNode *List;
7struct LNode
8{
9 ElementType Data;
10 List Next;
11};
12
13List MakeEmpty() {
14 List ptrl = NULL;
15 return ptrl;
16}
17
18int Length(List ptrl){
19 List p = ptrl ;
20 int cnt =0 ;
21 while (p){
22 p=p->Next;
23 cnt +=1;
24 }
25 return cnt ;
26}
27List FindKth(int i , List ptrl){
28 if (i<0){
29 printf("位置不合适、n");
30 return NULL ;
31 }
32 List p = ptrl ;
33 int j = 0;
34 while (j<i && p!=NULL ){
35 j+=1;
36 p=p->Next ;
37 }
38 if ( j ==i ) {
39 return p ;
40 }
41 return NULL;
42}
43
44List Find(ElementType x, List ptrl) {
45 List p = ptrl ;
46 while (p!=NULL && p->Data !=x){
47 p= p->Next;
48 }
49 return p ;
50}
51
52List Insert( ElementType x, int i, List ptrl ) {
53 if (i == 0 ){
54 List h = (List) malloc(sizeof(struct LNode));
55 h->Data = x ;
56 h->Next = ptrl ;
57 return h ;
58 }
59
60 List p = FindKth(i-1,ptrl) ;
61 if (p == NULL){
62 printf("参数i错误\n");
63 return NULL;
64 }
65
66 List s = (List) malloc(sizeof(struct LNode));
67 s->Data =x ;
68 s->Next = p->Next;
69 p->Next = s ;
70 return ptrl;
71
72}
73List Delete(int i , List ptrl){
74 if (i == 0 ){
75 List s = ptrl ;
76 if (!ptrl) {
77 free(s);
78 return NULL;
79 }
80 ptrl = ptrl->Next ;
81 free(s);
82 return ptrl ;
83 }
84
85 List p = FindKth(i-1,ptrl) ;
86 if (p == NULL){
87 printf("参数i错误\n");
88 return NULL;
89 }
90
91 List s = p->Next ;
92 p->Next = s->Next ;
93 free(s);
94 return ptrl;
95}
96
97
98void Print(List ptrl) {
99 List p= ptrl ;
100 if (p == NULL){
101 printf("p == NULL\n");
102 return ;
103 }
104 while (p){
105 printf("%d ", p ->Data);
106 p=p->Next ;
107 }
108 printf("\n");
109}
110
111
112int main() {
113 List ptrl;
114 List index ;
115
116 ptrl = MakeEmpty();
117 ptrl = Insert(1,0,ptrl);
118 ptrl = Insert(2,1,ptrl);
119 ptrl = Insert(3,2,ptrl);
120 ptrl = Insert(4,3,ptrl);
121 //Insert(5,4,ptrl);
122 // Insert(6,5,ptrl);
123 //Insert(6,7,ptrl);
124 Print(ptrl);
125 index = Find(3,ptrl);
126 printf("find %d in list index=%d\n ",3, index->Data);
127 Print(ptrl);
128
129 ptrl = Delete(0,ptrl);
130 Print(ptrl);
131 ptrl = Delete(2,ptrl);
132 Print(ptrl);
133 ptrl = Delete(0,ptrl);
134 Print(ptrl);
135 ptrl = Delete(0,ptrl);
136 Print(ptrl);
137 ptrl = Delete(0,ptrl);
138 Print(ptrl);
139 return 0;
140}
141