day19-線性表（順序表）（鏈表I）

一、補充

安裝軟件命令： sudo apt-get install? (軟件名)

安裝格式化對齊：sudo apt-get install clang-format
內存泄漏檢測工具：?sudo?apt-get?install?valgrind

? ? ? ? 編譯后，使用命令? ? ? ? ?valgrind ./a.out????????即可看內存是否泄露

二、順序表的基本操作

? ? ? ? 表頭結構是可選項，但最好在使用中加上；

#ifndef _SEQLIST_H_
#define _SEQLIST_H_typedef struct person
{char name[32];char sex;int age;int score;
} DATATYPE;typedef struct list
{DATATYPE *head;int tlen;int clen;
} SeqList;
//創建順序表
SeqList *CreateSeqList(int len);
//銷毀順序表
int DestroySeqList(SeqList *list);
//遍歷順序表
int ShowSeqList(SeqList *list);
//尾插，在順序表最后插入元素
int InsertTailSeqList(SeqList *list, DATATYPE *data);
//判斷表是否滿
int IsFullSeqList(SeqList *list);
//判斷表是否為空表
int IsEmptySeqList(SeqList *list);
//按指定位置插入元素
int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos);
//根據名字，查找元素
int FindSeqList(SeqList *list, char *name);
//根據名字，修改指定元素
int ModifySeqList(SeqList *list, char *old, DATATYPE *newdata);
//根據名字，刪除指定元素
int DeleteSeqList(SeqList *list, char *name);
//清空表，清空表中已有元素
int ClearSeqList(SeqList *list);
//獲得表中有效元素的個數
int GetSizeSeqList(SeqList *list);
//獲得指定小標的元素本身
DATATYPE *GetItemSeqList(SeqList *list, int ind);
#endif

2.1?創建順序表

SeqList *CreateSeqList(int len)
{SeqList *sl = malloc(sizeof(SeqList));if (NULL == sl){fprintf(stderr, "CreateSeqList malloc error\n");return NULL;}sl->head = malloc(sizeof(DATATYPE) * len);if (NULL == sl->head){fprintf(stderr, "CreateSeqList malloc2 error\n");return NULL;}sl->tlen = len;sl->clen = 0;return sl;
}

2.2?判斷是否已滿

int IsFullSeqList(SeqList *list)
{if (NULL == list){fprintf(stderr, "IsFullSeqList paramter error\n");return 1;}return list->clen == list->tlen;
}

2.3??尾插，在順序表最后插入元素

int InsertTailSeqList(SeqList *list, DATATYPE *data)
{if (IsFullSeqList(list)){fprintf(stderr, "SeqList full\n");}memcpy(&list->head[list->clen], data, sizeof(DATATYPE));list->clen++;return 0;
}

2.4??遍歷順序表

int ShowSeqList(SeqList *list)
{int len = GetSizeSeqList(list);int i = 0;for (i = 0; i < len; ++i){printf("%s %c %d %d\n", list->head[i].name, list->head[i].sex,list->head[i].age, list->head[i].score);}return 0;
}

2.5?獲得表中有效元素的個數

int GetSizeSeqList(SeqList *list) 
{ return list->clen; 
}

2.6?判斷表是否為空表

int IsEmptySeqList(SeqList *list) 
{ return 0 == list->clen; 
}

2.7?根據名字，查找元素

int FindSeqList(SeqList *list, char *name)
{int i = 0, len = GetSizeSeqList(list);for (i = 0; i < len; ++i){if (0 == strcmp(list->head[i].name, name)){return i;}}return -1;
}

?2.8?獲得指定下標的元素本身

DATATYPE *GetItemSeqList(SeqList *list, int ind)
{if (NULL == list){return NULL;}int len = GetSizeSeqList(list);if (ind < 0 || ind >= len){return NULL;}return &list->head[ind];
}

2.9?按指定位置插入元素

int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos)
{if (IsFullSeqList(list)){return 1;}int len = GetSizeSeqList(list);if (pos < 0 || pos > len){return 1;}int i = 0;for (i = list->clen; i > pos; i--){// Head[i] = head[i - 1];memcpy(&list->head[i], &list->head[i - 1], sizeof(DATATYPE));}memcpy(&list->head[pos], data, sizeof(DATATYPE));list->clen++;return 0;
}

2.10??根據名字，刪除指定元素

int DeleteSeqList(SeqList *list, char *name)
{if (IsEmptySeqList(list)){return 1;}int ret = FindSeqList(list, name);if (-1 == ret){printf("not find\n");return 1;}else{int len = GetSizeSeqList(list);int i;for (i = ret; i < len - 1; i++){memcpy(&list->head[i], &list->head[i + 1], sizeof(DATATYPE));}list->clen--;}return 0;
}

2.11?根據名字，修改指定元素

int ModifySeqList(SeqList *list, char *old, DATATYPE *newdata)
{if (IsEmptySeqList(list)){return 1;}int ret = FindSeqList(list, old);if (-1 == ret){printf("not find\n");return 1;}memcpy(&list->head[ret], newdata, sizeof(DATATYPE));return 0;
}

?2.12?清空表，清空表中已有元素

int ClearSeqList(SeqList *list)
{list->clen = 0;return 0;
}

2.13?銷毀順序表

int DestroySeqList(SeqList *list)
{if (NULL == list){return 1;}free(list->head);free(list);return 0;
}

三、?線性表順序存儲的優點，缺點

3.1 優點

無需為表中的邏輯關系增加額外的存儲空間
可以快速隨機訪問元素O(1)

3.2 缺點

插入，刪除元素需要移動元素o(n)
無法動態存儲

四、鏈表（線性表的鏈式存儲）

????????目的：解決順序存儲的缺點，插入和刪除，動態存儲問題

?特點：

線性表鏈式存儲結構的特點是一組任意的存儲單位存儲線性表的數據元素，存儲單元可以是連續的，也可以不連續;
可以被存儲在任意內存未被占用的位置上,所以前面的順序表只需要存儲數據元素信息就可以了。在鏈式結構中還需要一個元素存儲下一個元素的地址
為了表示每個數據元素，a[i]與其直接后繼數據元素a[i+1]之間的邏輯關系，? ? ? ? ? ? ? ? ? ? ? ? ?對a[i]來說，除了存儲其本身的信息外，還需要存一個指示器直接后續的信息。
我們把存儲元素信息的域叫數據域，把存儲直接后繼位置的域叫指針域。這兩部分信息組成數據元素ai的存儲映像，叫結點(Node);

4.1 單向鏈表

next指針指向整個結點開始位置
自定義類型不支持嵌套定義，因為不知道分配多大的內存空間；即在typedef srtuct node中，struct node next;不可取? ? ? ? ? ? ? ? ? ? 但*next可取
內存中開辟空間，用指針去接表頭結構

typedef struct
{char name[10];char sex;int age;int score;
}DATATYPE;typedef struct _node_
{DATATYPE data;struct _node_ *next;
}LinkNode;typedef struct
{LinkNode *head;int clen;
}LinkList;

4.1.1?創建鏈表

LinkList *CreateLinklist()
{LinkList *ll = malloc(sizeof(LinkList));if(NULL == ll){fprintf(stderr, "CreateLinklist malloc");return NULL;}ll->head = NULL;ll->clen = 0;return ll;
}

4.1.2? 判斷鏈表是否為空

int IsEmptyLinkList(LinkList *ll)
{return  0 == ll->clen ;
}

4.1.3 頭插法

（1）鏈表為空(直接將head指向newnode)

（2）鏈表非空

int InsertHeadLinkList(LinkList *ll, DATATYPE *data)
{LinkNode *newnode = malloc(sizeof(LinkNode));if(NULL == newnode){fprintf(stderr, "InsertHeadLinkList malloc");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;if(IsEmptyLinkList(ll)){ll->head = newnode;}else{newnode->next = ll->head;ll->head = newnode;}ll->clen++;return 0;
}

?4.1.4 獲得表中有效元素的個數

int GetSizeLinkList(LinkList *ll)
{return ll->clen;
}

4.1.5 遍歷表中元素

使tmp->next來進行遍歷，借助循環?

int ShowLinkList(LinkList *ll)
{int len = GetSizeLinkList(ll);LinkNode *tmp = ll->head;int i;for(i = 0; i < len; ++i){printf("%s %c %d %d \n", tmp->data.name, tmp->data.sex,tmp->data.age, tmp->data.score);tmp = tmp->next;}return 0;
}

4.1.6 根據名字，尋找元素

DATATYPE *FindLinkList(LinkList *ll, char *name)
{LinkNode *tmp = ll->head;while (tmp) {if(0 == strcmp(tmp->data.name, name)){return &tmp->data;}tmp = tmp->next;}return NULL;
}

4.1.7 根據名字，刪除元素

通過比較tmp下一個的內容來控制，使tmp停于待刪結點的前一個結點?

int DeleteLinkList(LinkList* ll, char* name)
{LinkNode* tmp = ll->head;if (IsEmptyLinkList(ll)){return 1;}if (0 == strcmp(tmp->data.name, name)){ll->head = ll->head->next;free(tmp);ll->clen--;return 0;}while (tmp->next){if (0 == strcmp(tmp->next->data.name, name)){LinkNode* tmp2 = tmp->next;tmp->next = tmp->next->next;free(tmp2);ll->clen--;return 0;}tmp = tmp->next;}return 1;
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/83572.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/83572.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/83572.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！