数据结构复习0---线性表

1.数组实现线性表

  1 /*数组实现线性表*/
  2 
  3 /*对于线性结构，有12种基本的操作，分别是：初始化、删除、清空、判断是否为空、
  4 遍历、求表的长度、求某个元素在表中的位置、返回特定序号的元素、求某个元素的前一个元素、
  5 求某个元素的后一个元素、插入一个元素、删除一个元素*/ 
  6 
  7 #include <stdio.h>
  8 #include <malloc.h>
  9 typedef int ElemType;
 10 typedef struct arraylist{ 
 11     ElemType *Array;//实际存放元素的数组
 12     int length;    //数组中已经使用了多少元素
 13     int size;   //数组的容量
 14 }arrayList;
 15 
 16 //初始化顺序表：给出初始化长度
 17 bool initialArray(arrayList *arrLst,int len){
 18     arrLst->length = 0;
 19     arrLst->size = len;    
 20     arrLst->Array = (ElemType*)malloc(len*sizeof(ElemType));
 21     if(NULL == arrLst->Array)
 22         return false;
 23     else
 24         return true;  
 25 }
 26 
 27 //删除顺序表
 28 void deleteArray(arrayList *arrLst){
 29     arrLst->length = 0;
 30     arrLst->size = 0;
 31     free(arrLst->Array);
 32     arrLst->Array = NULL;
 33 }
 34 
 35 //清空顺序表
 36 void clearArray(arrayList *arrLst){
 37     arrLst->length = 0;
 38 }
 39 
 40 //判断是否为空
 41 bool is_empty(arrayList *arrLst){
 42     if(0 == arrLst->length){
 43         printf("the arrayList is empty!
");
 44         return true;
 45     }
 46     else
 47     {
 48         printf("the arrayList is not empty!
");
 49         return false;        
 50     }
 51 }
 52 
 53 //求有多少个元素
 54 int arrayLength(arrayList *arrLst){
 55     return arrLst->length;
 56 }
 57 
 58 //取出某个元素
 59 bool getElem(arrayList *arrLst,int index,ElemType *e){
 60     if(index < 0 || index > arrayLength(arrLst)-1)
 61         return false;
 62     else
 63     {
 64         *e = arrLst->Array[index];
 65         return true;
 66     }
 67 
 68 }
 69 
 70 //遍历顺序表，并打印
 71 void printArray(arrayList *arrLst)
 72 {
 73     printf("array elements are: ");
 74     for(int i = 0; i < arrayLength(arrLst);++i)
 75     {
 76         printf("%d	",arrLst->Array[i]);
 77     }
 78     printf("
");
 79 }
 80 
 81 //判断某个元素的位置
 82 int locateElem(arrayList *arrLst,ElemType e)
 83 {
 84     for(int i = 0; i < arrayLength(arrLst);++i)
 85     {
 86         if(e == arrLst->Array[i])
 87             return i;
 88     }
 89     return -1;
 90 
 91 }
 92 
 93 //求某个元素的前驱：如果没找到返回-2；如果是第一个元素。返回-1；否则返回前驱元素的下标
 94 int preElement(arrayList *arrLst,ElemType e,ElemType *preElem)
 95 {
 96     for(int i = 0 ; i < arrayLength(arrLst); ++i)
 97     {
 98         //如果找到了
 99         if(e == arrLst->Array[i])
100         {
101             //如果是第一个元素
102             if(0 == i)
103             {
104                 return -1;
105             }
106             else
107             {
108                 *preElem = arrLst->Array[i-1];
109                 return i-1;
110             }
111         }
112     }
113     return -2;
114 }
115 
116 //求某个元素的后继：如果没找到，返回-2,如果是最后一个元素，返回-1；否则返回后继元素的下标
117 int nextElement(arrayList *arrLst,ElemType e,ElemType *nxtElem)
118 {
119     for(int i = 0; i < arrayLength(arrLst); ++i)
120     {
121         if(e == arrLst->Array[i])
122         {
123             if(arrayLength(arrLst) -1 == i)
124             {
125                 return -1;
126             }
127             else
128             {
129                 *nxtElem = arrLst->Array[i+1];
130                 return i+1;
131             }
132         }
133     }
134     return -2;
135 }
136 
137 //将元素插入到指定位置
138 bool insertElem(arrayList *arrLst,int index ,ElemType e )
139 {
140     //先判断插入位置是否合法
141     if(0 > index ||  arrayLength(arrLst) < index)
142         return false;
143 
144     //如果顺序表存储空间已满，则需要重新分配内存
145     if(arrLst->length == arrLst->size)
146     {
147         arrLst->Array = (ElemType*)realloc(arrLst->Array,2*arrLst->size*sizeof(ElemType));
148         if(NULL == arrLst->Array)
149             //分配失败，程序退出
150             return false;
151         else
152             //分配成功，扩容
153             arrLst->size *= 2;
154     }
155     //将插入点之后的元素后移
156     for(int i = arrayLength(arrLst); i > index; --i)
157         arrLst->Array[i] = arrLst->Array[i-1];
158     //插入元素
159     arrLst->Array[index] = e;
160     //顺序表长度自增
161     ++arrLst->length;
162     return true;
163 }
164 
165 bool deleteElem(arrayList *arrLst,int index ,ElemType *e)
166 {
167     if(index < 0 || index > arrayLength(arrLst)-1)
168         return false;
169     *e = arrLst->Array[index];
170     //将删除点的元素依次左移
171     for(int i = index; i < arrayLength(arrLst);++i)
172     {
173         arrLst->Array[i] = arrLst->Array[i+1];
174     }
175     --arrLst->length;;
176     return true;
177 }
数组实现线性表

2.链表实现线性表

  1 /* 链表实现线性表 */ 
  2 
  3 #include <stdio.h>
  4 #include <malloc.h>
  5 typedef int ElemType;
  6 typedef struct LNode{
  7     //存放的数据
  8     ElemType data;
  9     //指向下个节点的指针
 10     LNode *next;
 11 }LNode,*LinkList;
 12 
 13 //初始化链表
 14 bool initList(LinkList *lst){
 15     *lst = (LinkList)malloc(sizeof(LNode));
 16     if(NULL == lst)
 17         return false;
 18     (*lst)->next = NULL;
 19     return true;
 20 }
 21 
 22 //删除链表
 23 void deleteList(LinkList *lst)
 24 {
 25     LinkList p = (*lst)->next;
 26     LinkList q;
 27     while(p)
 28     {
 29         q = p->next;
 30         free(p);
 31         p = q;
 32     }
 33     free(*lst);
 34     *lst = NULL;
 35 }
 36 
 37 //清空链表
 38 void clearList(LinkList *lst)
 39 {
 40     LinkList p = (*lst)->next;
 41     LinkList q;
 42     while(p)
 43     {
 44         q = p->next;
 45         free(p);
 46         p = q;        
 47     }
 48     (*lst)->next = NULL;
 49 }
 50 
 51 //判断链表是否为空
 52 bool is_empty(LinkList *lst)
 53 {
 54     if(NULL == (*lst)->next)
 55     {
 56         printf("the list is empty! 
");
 57         return true;
 58     }
 59     else
 60     {
 61         printf("the list is not empty! 
");
 62         return false;
 63     }
 64 }
 65 
 66 //遍历链表并打印
 67 void printList(LinkList *lst){
 68     printf("list elements are: ");
 69     LinkList p = (*lst)->next;
 70     while(p){
 71         printf("%d",p->data);
 72         p = p->next;
 73     }
 74     printf("
");
 75 }
 76 
 77 //计算链表中的元素个数
 78 int listLength(LinkList *lst){
 79     int cnt = 0;
 80     LinkList p = (*lst)->next;
 81     while(p)
 82     {
 83         ++cnt;
 84         p = p->next;
 85     }
 86     return cnt;
 87 }
 88 
 89 //在指定位置插入元素
 90 bool insertElem(LinkList *lst,int index,ElemType *e){
 91     int cnt = 0;
 92     LinkList p = (*lst);
 93     LinkList q = (LinkList)malloc(sizeof(LNode));
 94     while(p)
 95     {
 96         if(index == cnt)
 97         {
 98             //新插入节点的指针指向当前节点的指针指向的元素
 99             q->next = p->next;
100             //当前节点的指针指向新插入的节点
101             p->next = q;
102             //存入数据
103             q->data = *e;
104             return true;
105         }
106         ++cnt;
107         p = p->next;
108     }
109     return false;
110 }
111 
112 //删除某个位置的元素
113 bool deleteElem(LinkList *lst,int index,ElemType *e)
114 {
115     int cnt = 0;
116     LinkList p = (*lst)->next;
117     //存储当前节点的前一个节点
118     LinkList q = *lst;
119     while(p)
120     {
121         
122         if(index == cnt)
123         {
124             //获取即将删除的节点的元素
125             *e = p->data;
126             //当前节点的前一个节点指向当前节点的后一个节点
127             q->next = p->next;
128             //释放当前节点
129             free(p);
130             break;
131         }
132         p = p->next;
133         q = q->next;
134         ++cnt;
135     }
136     return false;
137 }
138 
139 //获取某个元素的位置
140 int locateElem(LinkList *lst,ElemType e)
141 {
142     int index = 0;
143     LinkList p = (*lst)->next;
144     while(p)
145     {
146         if(e == p->data)
147             return index;
148 
149         ++index;
150         p = p->next;
151     }
152     return -1;
153 }
154 
155 //获取某个位置的元素
156 bool getElem(LinkList *lst,int index,ElemType *e)
157 {
158     int cnt = 0;
159     LinkList p = (*lst)->next;
160     while(p)
161     {
162         if(index == cnt)
163         {
164             *e = p->data;
165             return true;
166         }
167         ++cnt;
168         p = p->next;
169     }
170     return false;
171 }
172 
173 
174 //获取下一个元素
175 bool nextElem(LinkList *lst,ElemType curr,ElemType *nxt){
176     LinkList p = (*lst)->next;
177     while(p){
178         if(curr == p->data)
179         {
180             *nxt = p->next->data;
181             return true;
182         }
183         p = p->next;
184     }
185     return false;
186 }
187 
188 //获取前一个元素
189 bool priorElem(LinkList *lst,ElemType curr,ElemType *pre)
190 {
191     LinkList p = (*lst)->next;
192     LinkList q = (*lst);
193     while(p)
194     {
195         if(curr == p->data)
196         {
197             *pre = q->data;
198             return true;
199         }
200         q = q->next;
201         p = p->next;
202     }
203     return false;
204 }
205 
206 void inputList(LinkList *lst,int n,int* arr)
207 {
208     for(int i = n-1; i >= 0; --i)
209     {
210         LinkList pnew = (LinkList)malloc(sizeof(LNode));
211         pnew->data = arr[i];
212         pnew->next = (*lst)->next;
213         (*lst)->next = pnew;
214     }
215 }
链表实现线性表

3.双向链表

 1 /*双向链表*/
 2 
 3 #include <stdio.h>
 4 #include <malloc.h>
 5 #define ElemType int 
 6 typedef struct DNode
 7 {
 8     ElemType data;
 9     DNode *next;
10     DNode *prior;
11 }DNode,*DLinkList;
12 
13 bool initDList(DLinkList* dlst){
14     *dlst = (DLinkList)malloc(sizeof(DNode));
15     if(*dlst == NULL)
16         return false;
17     (*dlst)->next = NULL;
18     (*dlst)->prior = NULL;
19     return true;
20 }
21 
22 void deleteDList(DLinkList* dlst){
23     DLinkList p = (*dlst)->next;
24     DLinkList q;
25     while(p)
26     {
27         q = p->next;
28         free(p);
29         p = q;
30     }
31     free(*dlst);
32     *dlst = NULL;
33 }
34 
35 bool insertElem(DLinkList* dlst,int index,ElemType e)
36 {
37     int cnt = 0;
38     DLinkList p = *dlst;
39     while(p)
40     {
41         if(index == cnt)
42         {
43             DLinkList pnew = (DLinkList)malloc(sizeof(DNode));
44             pnew->data = e;
45             pnew->next = p->next;
46             pnew->prior = p;
47             p->next = pnew ;
48             //注意：当第一次插入元素或者在最后一个位置插入元素时，p->next是空的，并没有节点            
49             if(pnew->next!=NULL)
50                 pnew->next->prior = pnew;                    
51             return true;
52         }
53         p = p->next;
54         ++cnt;
55     }
56     return false;
57 
58 }
59 
60 void deleteElem(DLinkList* dlst,int index,ElemType *e){
61     int cnt = 0;
62     DLinkList p = (*dlst)->next;
63     while(p)
64     {
65         if(index == cnt)
66         {
67             *e = p->data;
68             p->prior->next = p->next;
69             //如果删除的是链表末尾的元素，则不需要这个步骤
70             if(p->next != NULL)
71                 p->next->prior = p->prior;
72             
73             free(p);            
74             break;
75         }
76         ++cnt;
77         p = p->next;
78     } 
79 }
80 
81 void printList(DLinkList* dlst){
82     printf("elements are: ");
83     DLinkList p = (*dlst)->next;
84     while(p)
85     {
86         printf("%d	",p->data);
87         p = p->next;
88     }
89     printf("
");
90 }
91 
92
双向链表

4.静态链表

  1 /*静态链表 */
  2 
  3 #include <stdio.h>
  4 #define N 100
  5 typedef struct{
  6     char data;
  7     int  cur;//游标域或者指针域
  8 }SList;
  9 
 10 void init_sl(SList slist[]){//初始化成空闲静态链表，
 11     int i;
 12     for(i=0;i<N-1;i++)
 13     {
 14         slist[i].cur=i+1;
 15     }
 16     slist[N-1].cur=0;    //最后一个指针域指向0
 17 }
 18 
 19 int malloc_sl(SList slist[]){//分配空闲节点
 20     int i=slist[0].cur;//总是取头结点之后的第一个空闲结点做分配，同时空闲链表非空，头结点做调整
 21     if (i)
 22     {
 23         slist[0].cur=slist[i].cur;//空闲链表头结点调整指针域
 24     }
 25     return i;//返回申请到的空闲节点的数组下标
 26 }
 27 
 28 
 29 void free_sl(SList slist[],int k){//将k节点回收
 30     slist[k].cur=slist[0].cur;//总是将回收的节点放在头结点之后
 31     slist[0].cur=k;
 32 }
 33 
 34 
 35 int difference_sl(SList slist[],int n){
 36     int i,m,q,p;
 37     char tmp[2];//为避免出现scanf输入字符出现接受回车符，则采用输入字符串的形式
 38     int start,end;//start是哨兵，end指向最后的节点
 39     init_sl(slist);//初始化 
 40     start=malloc_sl(slist);//从空闲链表中取出第一个空闲节点生成链表的头结点
 41     //注意区分，现在是有一个空闲链表是slist，里面都是空闲节点，每次申请malloc_sl和free_sl都是操作的是slist
 42     //然后非空静态链表，即集合A的链表是由start这个下标指引一直向后走，end指向非空链表的尾节点，
 43     //而且你发现start基本上都是1，因为开始的时候slist都是空闲节点，而分配又都是从头结点slist[0]之后的第一个
 44     //节点，即slist[1]开始分配，所以start=1
 45     end=start;
 46     while (n--){
 47         scanf("%s",tmp);
 48         i=malloc_sl(slist);
 49         slist[i].data=tmp[0];
 50         slist[end].cur=i;
 51         end=i;//end指针后移
 52     }
 53     slist[end].cur=0;//这个勿忘!尾节点的指针为空
 54     //至此A集合输入完毕，然后处理B集合
 55     scanf("%d",&m);
 56     while (m--)
 57     {
 58         scanf("%s",tmp);
 59         //从A集合中扫描，如果A中存在tmp，则在A中删除(free_sl)，即A-B，如果没有则添加入A，即B-A
 60         q=start;//q是p的前驱
 61         p=slist[start].cur;
 62         while (p!=slist[end].cur&&slist[p].data!=tmp[0])
 63         {
 64             q=p;
 65             p=slist[p].cur;
 66         }
 67         if (p!=slist[end].cur)//说明在A中找到了tmp，则删除
 68         {
 69             slist[q].cur=slist[p].cur;//跨过p节点
 70             free_sl(slist,p);
 71             if (end==p)
 72             {
 73                 end=q;//如果删除的是尾节点，则修改尾节点指针
 74             }
 75         }else{
 76             i=malloc_sl(slist);
 77             slist[i].data=tmp[0];
 78             slist[i].cur=slist[end].cur;
 79             slist[end].cur=i;//插在end后，end位置不变，因为end是标志集合A的结束，但是这里你也可以变化end指针，就是加上end=i即可
 80         }
 81     }
 82     return start;
 83 }
 84 
 85 
 86 void print_sl(SList slist[],int start){
 87     int p=slist[start].cur;
 88     while (p)
 89     {
 90         printf("%c ",slist[p].data);
 91         p=slist[p].cur;
 92     }
 93     printf("
");
 94 }
 95 
 96 
 97 int main(){
 98     int n,start;
 99     SList slist[N];
100     freopen("1.txt","r",stdin);
101     //该程序是求(A-B)U(B-A)集合运算
102     while (scanf("%d",&n)==1)
103     {
104         start=difference_sl(slist,n);
105         print_sl(slist,start);
106     }
107     fclose(stdin);
108     return 0;
109 }
静态链表

5.约瑟夫环

http://poj.org/problem?id=1012

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/liugl7/p/5621301.html