顺序链表
顺序存储链表结构体¶
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 | #ifndef _SEQLIST_H_ #define _SEQLIST_H_ typedef struct _tag_SeqList /* 头节点,记录表的信息 */ { int capacity; /* 表容量 */ int length; /* 表长度 */ int *node; /* node[capacity],为指针素组 char **node; */ }TSeqList; typedef void SeqList; typedef void SeqListNode; SeqList *SeqList_Create(int capacity); /* 创建顺序表 */ void SeqList_Destory(SeqList *list); /* 销毁顺序表 */ void SeqList_Clear(SeqList *list); /* 清空顺序表 */ int SeqList_Length(SeqList *list); /* 获取顺序表长度 */ int SeqList_Capacity(SeqList *list); /* 获取顺序表容量 */ /* 在pos位置插入元素 */ int SeqList_Insert(SeqList *list,SeqListNode *node,int pos); /* 获取pos位置的元素 */ SeqList *SeqList_Get(SeqList *list,int pos); /* 删除pos位置的元素 */ SeqList *SeqList_Delete(SeqList *list, int pos); #endif |
顺序存储链表实现¶
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 | #include<stdio.h> #include<stdlib.h> #include<string.h> #include "SeqList.h" /* 创建顺序表,返回值为SeqList*类型,即顺序表的地址 */ SeqList *SeqList_Create(int capacity) { int ret; TSeqList *temp=NULL; temp=(TSeqList*)malloc(sizeof(TSeqList)); /* 为头节点分配地址 */ if(temp==NULL) { ret=1; printf("func SeqList_Create() error:%d\n",ret); return NULL; } memset(temp, 0, sizeof(TSeqList)); temp->capacity=capacity; temp->length=0; /* 分配一个指针数组 char**malloc(sizeof(char*)*capacity) */ temp->node=(int*)malloc(sizeof(void*)*capacity); if(temp->node==NULL) { ret=2; printf("func SeqList_Create() error:%d\n",ret); return NULL; } return temp; } int SeqList_Capacity(SeqList *list) /* 求顺序表容量 */ { TSeqList *temp=NULL; if(list==NULL) { return; } temp=(TSeqList *)list; return temp->capacity; } int SeqList_Length(SeqList *list) /* 获取顺序表长度 */ { TSeqList *temp=NULL; if(list==NULL) { return; } temp=(TSeqList *)list; return temp->length; } /* 插入元素 */ int SeqList_Insert(SeqList *list,SeqListNode *node,int pos) { int i; TSeqList *temp=NULL; if(list==NULL || node==NULL) /* 健壮性判断 */ { return -1; } temp=(TSeqList *)list; if(temp->length >= temp->capacity) /* 如果顺序表已满 */ { return -2; } /* 如果给出的pos位置在线性表长度之后,即中间有空余 */ if(pos >temp->length) { pos=temp->length; /* 就修正到最后一个元素后面 */ } /* 将插入元素后的元素依次后移 */ for(i=temp->length;i>pos;i--) { temp->node[i]=temp->node[i-1]; } /* 腾出的位置插入新元素 */ temp->node[i]=(SeqListNode *)node; temp->length++; /* 插入成功后,长度加1 */ return 0; } SeqList *SeqList_Delete(SeqList *list, int pos) /* 删除元素 */ { int i; TSeqList *tlist=NULL; SeqListNode *temp=NULL; tlist=(TSeqList*)list; if(list==NULL || pos<0 || pos>=tlist->capacity) { printf("SeqList_Detele() error\n"); return NULL; } temp=(SeqListNode*)tlist->node[pos]; /* 要删除的元素 */ for(i=pos+1;i<tlist->length;i++) { tlist->node[i-1]=tlist->node[i]; } tlist->length--; return temp; } SeqList *SeqList_Get(SeqList *list, int pos) /* 查找元素 */ { TSeqList *tlist=NULL; SeqListNode *temp=NULL; tlist=(TSeqList *)list; if(list==NULL || pos<0 || pos>=tlist->capacity) { printf("SeqList_Get() error\n"); return NULL; } /* 将表中pos位置的结点指针赋给temp */ temp=(SeqListNode *)tlist->node[pos]; return temp; } void SeqList_Clear(SeqList *list) /* 清空顺序表 */ { TSeqList *temp=NULL; if(list==NULL) { return; } temp=(SeqList*)list; temp->length=0; memset(temp->node, 0, (temp->capacity*sizeof(void*))); return; } void SeqList_Destory(SeqList *list) /* 销毁顺序表 */ { TSeqList *temp=NULL; if(list==NULL) { return; } temp=(TSeqList *)list; if(temp->node != NULL) { free(temp->node); /* 先释放头节点中的指针数组 */ } free(temp); /* 在释放头节点 */ return; } |
Unit Test¶
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 | #include<stdio.h> #include<stdlib.h> #include<string.h> #include "SeqList.h" typedef struct _Teacher { char name[32]; int age; }Teacher; int main() { int ret =0; int len =0; int i =0; SeqList *list=NULL; Teacher t1={ "loci", 32 }; Teacher t2={ "coco", 23 }; Teacher t3={ "lili", 21 }; Teacher t4={ "fgfg", 45 }; Teacher t5={ "ktkt", 28 }; /* 创建顺序表 */ list=SeqList_Create(10); /* 头插法 */ ret=SeqList_Insert(list,(SeqListNode*)&t1,0); ret=SeqList_Insert(list,(SeqListNode*)&t2,0); ret=SeqList_Insert(list,(SeqListNode*)&t3,0); ret=SeqList_Insert(list,(SeqListNode*)&t4,0); ret=SeqList_Insert(list,(SeqListNode*)&t5,0); printf("顺序表容量:%d\n",SeqList_Capacity(list)); printf("顺序表长度:%d\n",SeqList_Length(list)); len=SeqList_Length(list); printf("遍历顺序表:\n"); for(i=0;i<len; i++) { Teacher *temp=(Teacher *)SeqList_Get(list,i); if(temp==NULL) { printf("func SeqList_Get() error\n"); return; } printf("teachr name:%s\tage:%d\n",temp->name,temp->age); } printf("销毁顺序表:\n"); while(SeqList_Length(list)>0) { /* 删除头部元素 */ Teacher *temp=(Teacher *)SeqList_Delete(list,0); if(temp==NULL) { printf("func SeqList_Delete error\n"); return; } printf("teachr name:%s\tage:%d\n",temp->name,temp->age); } SeqList_Destory(list); system("pause"); return 0; } |