1.基本概念
线性表：n个数据类型相同元素的有限序列。（比如矩阵，数组，字符串，堆栈，队列等）。
特点：第一个元素无直接前趋，最后一个元素无直接后继，其余元素都有一个直接前趋和一个直接后继。
存储结构：线性存储结构，链式存储结构。
2.练习
（1）两个递增顺序表（顺序存储），la，lb，顺序插入顺序表lc中。
#include#include #define SIZE 6#define END 9999#define CHARGE 0typedef int ElemType;typedef struct list { ElemType elem[15]; int last;} SeqList;void initList(SeqList *l){ int index = 0; int midleVarile = 0; printf("if you want to exit please input 9999\n"); printf("please input intger:"); while(1) { scanf("%d", &midleVarile); if(midleVarile == END) { break; } else { l->elem[index] = midleVarile; } index++;// fflush(stdin); } l->last = index;}void mergeList(SeqList *l1, SeqList *l2, SeqList *l3){ int index1 = 0; int index2 = 0; int index3 = 0; int midleInt = 0; while((index1 != (l1->last)) && (index2 != (l2->last))) { if(l1->elem[index1] <= l2->elem[index2]) { midleInt = l1->elem[index1]; l3->elem[index3] = midleInt; index1++; index3++; } else { midleInt = l2->elem[index2]; l3->elem[index3] = midleInt; index2++; index3++; } } if(index1 == (l1->last)) { for( ; index2 != (l2->last); index2++, index3++) { l3->elem[index3] = l2->elem[index2]; } } else { for(; index1 != (l1->last); index1++, index3++) { l3->elem[index3] = l1->elem[index1]; } } l3->last = l1->last + l2->last;}void outList(SeqList *l){ int index = 0; int i; for(i = 0; i < l->last; i++) { printf("%d ", l->elem[i]); }}int main(){ SeqList l1; SeqList l2; SeqList l3; initList(&l1); initList(&l2); mergeList(&l1, &l2, &l3); outList(&l3);}
（2）代码功能如下，后期会继续增加，当作复习用。
1 #include2 #include 3 4 #define OK 1 5 #define ERROR 0 6 #define OVERFLOW -2 7 8 typedef int ElemType; 9 10 typedef struct Node 11 { 12 ElemType data; 13 struct Node *next; 14 } Node, *LinkList; 15 16 // 创建新链表 17 Node * NewLinkList() 18 { 19 Node *node = (Node *)malloc(sizeof(Node)); 20 node->next = NULL; 21 return node; 22 } 23 24 //初始化链表 25 void InitLinkList(LinkList l) 26 { 27 // Node * l1; 28 int midleInt = 0; 29 30 printf("please input intger end with 9999:"); 31 32 while(midleInt != 9999) 33 { 34 scanf("%d", &midleInt); 35 l->next = (Node *)malloc(sizeof(Node)); 36 l = l->next; 37 l->next = NULL; 38 l->data = midleInt; 39 } 40 } 41 42 //得到链表的长度 43 unsigned int getListLength(LinkList l) 44 { 45 int lLength = 0; 46 47 l = l->next; 48 49 if(l == NULL) 50 return 0; 51 52 while(l != NULL) 53 { 54 lLength++; 55 l = l->next; 56 } 57 58 return lLength; 59 } 60 61 //链表的反转 62 LinkList ReverseList(LinkList l) 63 { 64 LinkList l1 = NewLinkList(); 65 LinkList l2; 66 LinkList l3 = l; 67 68 69 if((l->next == NULL) || (l->next->next == NULL)) 70 return l; 71 72 l = l->next; 73 74 while(l != NULL) 75 { 76 l2 = l1->next; 77 l3 = l->next; 78 l1->next = l; 79 l->next = l2; 80 l = l3; 81 } 82 83 return l1; 84 } 85 86 //链表清空 87 void LinkListClear(LinkList l) 88 { 89 l->next = NULL; 90 } 91 92 //链表是否为空 93 int LinkListisEmpty(LinkList l) 94 { 95 if(l->next == NULL) 96 return 1; 97 else 98 return 0; 99 }100 101 //链表遍历102 void LinkListTraverse(LinkList l)103 {104 // LinkList l1 = l;105 l = l->next;106 107 while(l != NULL)108 {109 printf("%d ", l->data);110 111 l = l->next;112 }113 printf("\n");114 }115 116 int main(void)117 {118 LinkList l = NewLinkList();119 InitLinkList(l);120 LinkListTraverse(l);121 l = ReverseList(l);122 LinkListTraverse(l);123 }
后面会继续增加
//算法思想：定义两个节点指针，让第一个节点指针首先后移k个节点，然后让另一个指针和第一个指针同时后移，知道第一个指针到达尾部。 //注意：当链表节点总数小于k时，或者k为0时候，或者链表为空时候。 1 //查找单链表中倒数第k个节点 2 Node * GetAKNode(LinkList l, int k) 3 { 4 Node *l1 = l; 5 Node *l2 = l; 6 LinkList l3 = l; 7 int nodeLength; 8 9 l3 = l3->next;10 nodeLength = getListLength(l3);11 12 if((l3 == NULL) || (nodeLength < k) || (k == 0))13 return NULL;14 15 while(k)16 {17 k--;18 l1 = l1->next;19 }20 21 while(l1 != NULL)22 {23 l1 = l1->next;24 l2 = l2->next;25 }26 27 return l2;28 }29 //算法思想：定义两个指针，第一个节点后移一个单位，第二个节点后移两个单位，当第二个节点到达尾部的时候，第一个节点指向中间节点的位置。 //注意：当只有1个节点，或者，为空的时候，直接返回头节点。30 //获得单链表中间节点31 Node *GetMNode(LinkList l)32 {33 Node *l1 = l;34 Node *l2 = l;35 36 if((l->next == NULL) || (l == NULL))37 return l;38 39 while(l1 != NULL)40 {41 l1 = l1->next;42 l2 = l2->next;43 44 if(l1 != NULL)45 {46 l1 = l1->next;47 }48 }49 50 return l2;51 }
//判断单链表是否有环 //算法思想：两个指针，快的每次走两步，慢的，每次走一步，如果相交则有环，快的走到空，则无环。 1 int hasCircle(LinkList l) 2 { 3 Node * l1 = l; 4 Node * l2 = l; 5 6 if(l->next == NULL) 7 return 0; 8 9 while(l1 == NULL)10 {11 l1 = l1->next;12 l2 = l2->next;13 14 if(l1 != NULL)15 l1 = l1->next;16 17 if(l1 == l2)18 return 1;19 }20 21 return 0;22 }
//寻找两个链表的交点 //算法思想：招到较长的链，让较长的链的长度减去较短链的长度，然后让较长链的指针后移到和较短链相同长度的位置，然后同时后移，每次作比较，相同则为交点。 1 Node *GetFirstCommonNode(LinkList l1, LinkList l2) 2 { 3 Node *l3 = l1; 4 Node *l4 = l2; 5 int i3 = 0; 6 int i4 = 0; 7 8 if(l1->next == NULL || l2->next == NULL) 9 return NULL;10 11 l3 = l3->next;12 l4 = l4->next;13 l1 = l1->next;14 l2 = l2->next;15 16 while(l3 != NULL) 17 {18 i3++;19 l3 = l3->next;20 }21 22 while(l4 != NULL)23 {24 i4++;25 l4 = l4->next;26 }27 28 if(i3 >= i4)29 {30 i3 = i3 - i4;31 32 while(i3)33 {34 i3--;35 l1 = l1->next;36 }37 }38 else39 {40 i4 = i4 - i3;41 42 while(i4)43 {44 i4--;45 l2 = l2->next;46 }47 }48 49 while(l1 != l2)50 {51 l1 = l1->next;52 l2 = l2->next;53 }54 55 return l1;56 }
//删除data为k的节点，要求时间复杂度为0（1）//算法思想：先找到该节点，把后一个节点复制到本节点，删除后一个节点，如果要删除的节点是最后一个，则笨办法遍历到最后一个节点的前一个节点，删除。void Delete(LinkList l, int k){ Node * l1 = l; if(l->next == NULL) return; l1 = l->next; while(l1 != NULL) { if(l1->data == k) { if(l1->next == NULL) { while(1) { if(l->next == l1) { l->next = NULL; return ; } l = l->next; } } l1->data = l1->next->data; l1->next = l1->next->next; return ; } l1 = l1->next; }}
//双向链表的建立 #include#include typedef int ElemType;typedef struct Node { ElemType data; struct Node *pre; struct Node *next;}DList, *DListHead;void creat(DListHead *head){ int x = 0; DListHead l; DListHead l1; *head = (DList *)malloc(sizeof(DList)); l = *head; l->pre = NULL; l->data = x; while(x != -1) { scanf("%d", &x); l->next = (DListHead)malloc(sizeof(DList)); l1 = l->next; l1->data = x; l1->next = NULL; l1->pre = l; l = l->next; } l = l1->pre ; free(l1); l->next = NULL;}void print(DListHead *head){ DListHead head1 = *head; while(head1 ->next != NULL) { printf("%d ",head1->data); head1 = head1->next; } printf("\n"); while(head1->pre != NULL) { printf("%d ", head1->data); head1 = head1->pre; }}int main(){ DListHead head; creat(&head); print(&head);}