由于时间有限，直接贴教材上的单链表学习==
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
//单链表基本运算算法 #include <stdio.h> #include <malloc.h> typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; //指向后继结点 } LinkNode; //声明单链表结点类型 void CreateListF(LinkNode *&L,ElemType a[],int n) //头插法建立单链表 { LinkNode *s; L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点 L->next=NULL; for (int i=0;i<n;i++) { s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点s s->data=a[i]; s->next=L->next; //将结点s插在原开始结点之前,头结点之后 L->next=s; } } void CreateListR(LinkNode *&L,ElemType a[],int n) //尾插法建立单链表 { LinkNode *s,*r; L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点 L->next=NULL; r=L; //r始终指向终端结点,开始时指向头结点 for (int i=0;i<n;i++) { s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点s s->data=a[i]; r->next=s; //将结点s插入结点r之后 r=s; } r->next=NULL; //终端结点next域置为NULL } void InitList(LinkNode *&L)// 初始化表 { L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点 L->next=NULL; } void DestroyList(LinkNode *&L)//销毁表 { LinkNode *pre=L,*p=pre->next; while (p!=NULL) { free(pre); pre=p; p=pre->next; } free(pre); //此时p为NULL,pre指向尾结点,释放它 } bool ListEmpty(LinkNode *L)//判断是否为空 { return(L->next==NULL); } int ListLength(LinkNode *L)//求表长 { LinkNode *p=L;int i=0; while (p->next!=NULL) { i++; p=p->next; } return(i); } void DispList(LinkNode *L)//输出表 { LinkNode *p=L->next; while (p!=NULL) { printf("%d ",p->data); p=p->next; } printf("\n"); } bool GetElem(LinkNode *L,int i,ElemType &e)//求表中第i个数据元素的值 { int j=0; LinkNode *p=L; if (i<=0) return false; //i错误返回假 while (j<i && p!=NULL) { j++; p=p->next; } if (p==NULL) //不存在第i个数据结点 return false; else //存在第i个数据结点 { e=p->data; return true; } } int LocateElem(LinkNode *L,ElemType e)//从头开始找第一个值域与e相等的节点 { LinkNode *p=L->next; int n=1; while (p!=NULL && p->data!=e) { p=p->next; n++; } if (p==NULL) return(0); else return(n); } bool ListInsert(LinkNode *&L,int i,ElemType e)//将e的值插入到第i个节点后面 { int j=0; LinkNode *p=L,*s; if (i<=0) return false; //i错误返回假 while (j<i-1 && p!=NULL) //查找第i-1个结点p { j++; p=p->next; } if (p==NULL) //未找到位序为i-1的结点 return false; else //找到位序为i-1的结点*p { s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点*s s->data=e; s->next=p->next; //将s结点插入到结点p之后 p->next=s; return true; } } bool ListDelete(LinkNode *&L,int i,ElemType &e)//删除第i个结点 { int j=0; LinkNode *p=L,*q; if (i<=0) return false; //i错误返回假 while (j<i-1 && p!=NULL) //查找第i-1个结点 { j++; p=p->next; } if (p==NULL) //未找到位序为i-1的结点 return false; else //找到位序为i-1的结点p { q=p->next; //q指向要删除的结点 if (q==NULL) return false; //若不存在第i个结点,返回false e=q->data; p->next=q->next; //从单链表中删除q结点 free(q); //释放q结点 return true; } } |
下面是双链表的教材代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 |
//双链表基本运算算法 #include <stdio.h> #include <malloc.h> typedef int ElemType; typedef struct DNode //定义双链表结点类型 { ElemType data; struct DNode *prior; //指向前驱结点 struct DNode *next; //指向后继结点 } DLinkNode; void CreateListF(DLinkNode *&L,ElemType a[],int n) //头插法建双链表 { DLinkNode *s; L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点 L->prior=L->next=NULL; for (int i=0;i<n;i++) { s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点 s->data=a[i]; s->next=L->next; //将结点s插在原开始结点之前,头结点之后 if (L->next!=NULL) L->next->prior=s; L->next=s;s->prior=L; } } void CreateListR(DLinkNode *&L,ElemType a[],int n) //尾插法建双链表 { DLinkNode *s,*r; L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点 L->prior=L->next=NULL; r=L; //r始终指向终端结点,开始时指向头结点 for (int i=0;i<n;i++) { s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点 s->data=a[i]; r->next=s;s->prior=r; //将结点s插入结点r之后 r=s; } r->next=NULL; //尾结点next域置为NULL } void InitList(DLinkNode *&L) { L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点 L->prior=L->next=NULL; } void DestroyList(DLinkNode *&L) { DLinkNode *pre=L,*p=pre->next; while (p!=NULL) { free(pre); pre=p; p=pre->next; } free(pre); } bool ListEmpty(DLinkNode *L) { return(L->next==NULL); } int ListLength(DLinkNode *L) { DLinkNode *p=L; int i=0; while (p->next!=NULL) { i++; p=p->next; } return(i); } void DispList(DLinkNode *L) { DLinkNode *p=L->next; while (p!=NULL) { printf("%d ",p->data); p=p->next; } printf("\n"); } bool GetElem(DLinkNode *L,int i,ElemType &e) { int j=0; DLinkNode *p=L; if (i<=0) return false; //i错误返回假 while (j<i && p!=NULL) { j++; p=p->next; } if (p==NULL) return false; else { e=p->data; return true; } } int LocateElem(DLinkNode *L,ElemType e) { int n=1; DLinkNode *p=L->next; while (p!=NULL && p->data!=e) { n++; p=p->next; } if (p==NULL) return(0); else return(n); } bool ListInsert(DLinkNode *&L,int i,ElemType e) { int j=0; DLinkNode *p=L,*s; if (i<=0) return false; //i错误返回假 while (j<i-1 && p!=NULL) { j++; p=p->next; } if (p==NULL) //未找到第i-1个结点 return false; else //找到第i-1个结点p { s=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点s s->data=e; s->next=p->next; //将结点s插入到结点p之后 if (p->next!=NULL) p->next->prior=s; s->prior=p; p->next=s; return true; } } bool ListDelete(DLinkNode *&L,int i,ElemType &e) { int j=0; DLinkNode *p=L,*q; if (i<=0) return false; //i错误返回假 while (j<i-1 && p!=NULL) { j++; p=p->next; } if (p==NULL) //未找到第i-1个结点 return false; else //找到第i-1个结点p { q=p->next; //q指向要删除的结点 if (q==NULL) return false; //不存在第i个结点 e=q->data; p->next=q->next; //从单链表中删除*q结点 if (p->next!=NULL) p->next->prior=p; free(q); //释放q结点 return true; } } |
循环单链表的教材代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 |
//循环单链表基本运算算法 #include <stdio.h> #include <malloc.h> typedef int ElemType; typedef struct LNode //定义单链表结点类型 { ElemType data; struct LNode *next; } LinkNode; void CreateListF(LinkNode *&L,ElemType a[],int n) //头插法建立循环单链表 { LinkNode *s;int i; L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点 L->next=NULL; for (i=0;i<n;i++) { s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点 s->data=a[i]; s->next=L->next; //将结点s插在原开始结点之前,头结点之后 L->next=s; } s=L->next; while (s->next!=NULL) //查找尾结点,由s指向它 s=s->next; s->next=L; //尾结点next域指向头结点 } void CreateListR(LinkNode *&L,ElemType a[],int n) //尾插法建立循环单链表 { LinkNode *s,*r;int i; L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点 L->next=NULL; r=L; //r始终指向终端结点,开始时指向头结点 for (i=0;i<n;i++) { s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点 s->data=a[i]; r->next=s; //将结点s插入结点r之后 r=s; } r->next=L; //尾结点next域指向头结点 } void InitList(LinkNode *&L) { L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点 L->next=L; } void DestroyList(LinkNode *&L) { LinkNode *p=L,*q=p->next; while (q!=L) { free(p); p=q; q=p->next; } free(p); } bool ListEmpty(LinkNode *L) { return(L->next==L); } int ListLength(LinkNode *L) { LinkNode *p=L;int i=0; while (p->next!=L) { i++; p=p->next; } return(i); } void DispList(LinkNode *L) { LinkNode *p=L->next; while (p!=L) { printf("%d ",p->data); p=p->next; } printf("\n"); } bool GetElem(LinkNode *L,int i,ElemType &e) { int j=0; LinkNode *p; if (L->next!=L) //单链表不为空表时 { if (i==1) { e=L->next->data; return true; } else //i不为1时 { p=L->next; while (j<i-1 && p!=L) { j++; p=p->next; } if (p==L) return false; else { e=p->data; return true; } } } else //单链表为空表时 return false; } int LocateElem(LinkNode *L,ElemType e) { LinkNode *p=L->next; int n=1; while (p!=L && p->data!=e) { p=p->next; n++; } if (p==L) return(0); else return(n); } bool ListInsert(LinkNode *&L,int i,ElemType e) { int j=0; LinkNode *p=L,*s; if (p->next==L || i==1) //原单链表为空表或i==1时 { s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s s->data=e; s->next=p->next; //将结点s插入到结点p之后 p->next=s; return true; } else { p=L->next; while (j<i-2 && p!=L) { j++; p=p->next; } if (p==L) //未找到第i-1个结点 return false; else //找到第i-1个结点p { s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s s->data=e; s->next=p->next; //将结点s插入到结点p之后 p->next=s; return true; } } } bool ListDelete(LinkNode *&L,int i,ElemType &e) { int j=0; LinkNode *p=L,*q; if (p->next!=L) //原单链表不为空表时 { if (i==1) //i==1时 { q=L->next; //删除第1个结点 e=q->data; L->next=q->next; free(q); return true; } else //i不为1时 { p=L->next; while (j<i-2 && p!=L) { j++; p=p->next; } if (p==L) //未找到第i-1个结点 return false; else //找到第i-1个结点p { q=p->next; //q指向要删除的结点 e=q->data; p->next=q->next; //从单链表中删除q结点 free(q); //释放q结点 return true; } } } else return false; } |
循环双链表的教材代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 |
/循环双链表基本运算算法 #include <stdio.h> #include <malloc.h> typedef int ElemType; typedef struct DNode //定义双链表结点类型 { ElemType data; struct DNode *prior; //指向前驱结点 struct DNode *next; //指向后继结点 } DLinkNode; void CreateListF(DLinkNode *&L,ElemType a[],int n) //头插法建立循环双链表 { DLinkNode *s;int i; L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点 L->next=NULL; for (i=0;i<n;i++) { s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点 s->data=a[i]; s->next=L->next; //将结点s插在原开始结点之前,头结点之后 if (L->next!=NULL) L->next->prior=s; L->next=s;s->prior=L; } s=L->next; while (s->next!=NULL) //查找尾结点,由s指向它 s=s->next; s->next=L; //尾结点next域指向头结点 L->prior=s; //头结点的prior域指向尾结点 } void CreateListR(DLinkNode *&L,ElemType a[],int n) //尾插法建立循环双链表 { DLinkNode *s,*r;int i; L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点 L->next=NULL; r=L; //r始终指向尾结点,开始时指向头结点 for (i=0;i<n;i++) { s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点 s->data=a[i]; r->next=s;s->prior=r; //将结点s插入结点r之后 r=s; } r->next=L; //尾结点next域指向头结点 L->prior=r; //头结点的prior域指向尾结点 } void InitList(DLinkNode *&L) { L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点 L->prior=L->next=L; } void DestroyList(DLinkNode *&L) { DLinkNode *p=L,*q=p->next; while (q!=L) { free(p); p=q; q=p->next; } free(p); } bool ListEmpty(DLinkNode *L) { return(L->next==L); } int ListLength(DLinkNode *L) { DLinkNode *p=L; int i=0; while (p->next!=L) { i++; p=p->next; } return(i); } void DispList(DLinkNode *L) { DLinkNode *p=L->next; while (p!=L) { printf("%d ",p->data); p=p->next; } printf("\n"); } bool GetElem(DLinkNode *L,int i,ElemType &e) { int j=0; DLinkNode *p; if (L->next!=L) //双链表不为空表时 { if (i==1) { e=L->next->data; return true; } else //i不为1时 { p=L->next; while (j<i-1 && p!=L) { j++; p=p->next; } if (p==L) return false; else { e=p->data; return true; } } } else //双链表为空表时 return 0; } int LocateElem(DLinkNode *L,ElemType e) { int n=1; DLinkNode *p=L->next; while (p!=NULL && p->data!=e) { n++; p=p->next; } if (p==NULL) return(0); else return(n); } bool ListInsert(DLinkNode *&L,int i,ElemType e) { int j=0; DLinkNode *p=L,*s; if (p->next==L) //原双链表为空表时 { s=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点s s->data=e; p->next=s;s->next=p; p->prior=s;s->prior=p; return true; } else if (i==1) //原双链表不为空表但i=1时 { s=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点s s->data=e; s->next=p->next;p->next=s; //将结点s插入到结点p之后 s->next->prior=s;s->prior=p; return true; } else { p=L->next; while (j<i-2 && p!=L) { j++; p=p->next; } if (p==L) //未找到第i-1个结点 return false; else //找到第i-1个结点*p { s=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建新结点s s->data=e; s->next=p->next; //将结点s插入到结点p之后 if (p->next!=NULL) p->next->prior=s; s->prior=p; p->next=s; return true; } } } bool ListDelete(DLinkNode *&L,int i,ElemType &e) { int j=0; DLinkNode *p=L,*q; if (p->next!=L) //原双链表不为空表时 { if (i==1) //i==1时 { q=L->next; //删除第1个结点 e=q->data; L->next=q->next; q->next->prior=L; free(q); return true; } else //i不为1时 { p=L->next; while (j<i-2 && p!=NULL) { j++; p=p->next; } if (p==NULL) //未找到第i-1个结点 return false; else //找到第i-1个结点p { q=p->next; //q指向要删除的结点 if (q==NULL) return 0; //不存在第i个结点 e=q->data; p->next=q->next; //从单链表中删除q结点 if (p->next!=NULL) p->next->prior=p; free(q); //释放q结点 return true; } } } else return false; //原双链表为空表时 } |
两个表的拼接
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
//线性表的应用:两个表的简单自然连接的算法 #include <stdio.h> #include <malloc.h> #define MaxCol 10 //最大列数 typedef int ElemType; typedef struct Node1 //数据结点类型 { ElemType data[MaxCol]; struct Node1 *next; //指向后继数据结点 } DList; typedef struct Node2 //头结点类型 { int Row,Col; //行数和列数 DList *next; //指向第一个数据结点 } HList; void CreateTable(HList *&h) { int i,j; DList *r,*s; h=(HList *)malloc(sizeof(HList)); //创建头结点 h->next=NULL; printf("表的行数,列数:"); scanf("%d%d",&h->Row,&h->Col); for (i=0;i<h->Row;i++) { printf(" 第%d行:",i+1); s=(DList *)malloc(sizeof(DList)); //创建数据结点 for (j=0;j<h->Col;j++) //输入一行的数据初步统计 scanf("%d",&s->data[j]); if (h->next==NULL) //插入第一个数据结点 h->next=s; else //插入其他数据结点 r->next=s; //将结点s插入到结点r结点之后 r=s; //r始终指向最后一个数据结点 } r->next=NULL; //表尾结点next域置空 } void DispTable(HList *h) { int j; DList *p=h->next; while (p!=NULL) { for (j=0;j<h->Col;j++) printf("%4d",p->data[j]); printf("\n"); p=p->next; } } void LinkTable(HList *h1,HList *h2,HList *&h) { int f1,f2,i; DList *p=h1->next,*q,*s,*r; printf("连接字段是:第1个表位序,第2个表位序:"); scanf("%d%d",&f1,&f2); h=(HList *)malloc(sizeof(HList)); h->Row=0; h->Col=h1->Col+h2->Col; h->next=NULL; while (p!=NULL) { q=h2->next; while (q!=NULL) { if (p->data[f1-1]==q->data[f2-1]) //对应字段值相等 { s=(DList *)malloc(sizeof(DList)); //创建一个数据结点 for (i=0;i<h1->Col;i++) //复制表1的当前行 s->data[i]=p->data[i]; for (i=0;i<h2->Col;i++) s->data[h1->Col+i]=q->data[i]; //复制表2的当前行 if (h->next==NULL) //插入第一个数据结点 h->next=s; else //插入其他数据结点 r->next=s; r=s; //r始终指向最后数据结点 h->Row++; //表行数增1 } q=q->next; //表2下移一个记录 } p=p->next; //表1下移一个记录 } r->next=NULL; //表尾结点next域置空 } int main() { HList *h1,*h2,*h; printf("表1:\n"); CreateTable(h1); //创建表1 printf("表2:\n"); CreateTable(h2); //创建表2 LinkTable(h1,h2,h); //连接两个表 printf("连接结果表:\n"); DispTable(h); //输出连接结果 return 1; } |
