數(shù)據(jù)結構

?? ?相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。
?? ?

?邏輯結構

?? ?集合，所有數(shù)據(jù)在同一個集合中，關系平等。
???

線性，數(shù)據(jù)和數(shù)據(jù)之間是一對一的關系。數(shù)組就是線性表的一種。
???

樹， 一對多
??

?圖，多對多? ?? ?可能用在地圖里a

?

物理結構(在內(nèi)存當中的存儲關系)?

順序存儲，數(shù)據(jù)存放在連續(xù)的存儲單位中。邏輯關系和物理關系一致

??鏈式，數(shù)據(jù)存放的存儲單位是隨機或任意的，可以連續(xù)也可以不連續(xù)。

struct Per 數(shù)據(jù)元素
?? ?{
?? ??? ?char name;//? ? ? ? 數(shù)據(jù)項--》給數(shù)據(jù)賦予一定的意義
?? ??? ?int age;
?? ??? ?char phone;
?? ?}?? ?
?? ??? ??? ?
?? ?struct Per list[100]; //數(shù)據(jù)對象

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?結構體集合? ? ? ? ? ? ?
?? ??? ?
? ? ? ? ? 數(shù)據(jù)的類型，ADT ? ?abstruct datatype? 抽象數(shù)據(jù)類型
?? ??? ?是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。
?? ??? ?原子類型，int，char，float
?? ??? ?結構類型，sturct， union，

?? ??? ?抽象數(shù)據(jù)類型， 數(shù)學模型 + 操作。
?? ??? ?
?? ??? ?程序 = ?數(shù)據(jù) + 算法

算法，? ??

是解決特定問題求解步驟的描述，計算機中表現(xiàn)為指令的有限序列，每條指令表示一個或多個操作

?算法的特征，

?1，輸入，輸出特性，輸入時可選的，輸出時必須的。（輸出是必須有某個東西會改變）
?? ?2，有窮性，執(zhí)行的步驟會自動結束，不能是死循環(huán)，并且每一步是在可以接受的時間內(nèi)完成。
?? ?3，確定性，同一個輸入，會得到唯一的輸出。
?? ?4，可行性，每一個步驟都是可以實現(xiàn)的.
??

?算法的設計，??

?1，正確性，
?? ??? ?語法正確
?? ??? ?合法的輸入能得到合理的結果。
?? ??? ?對非法的輸入，給出滿足要求的規(guī)格說明
?? ??? ?對精心選擇，甚至刁難的測試都能正常運行，結果正確
?? ?2，可讀性，便于交流，閱讀? A，理解
?? ?3，健壯性，輸入非法數(shù)據(jù)，能進行相應的處理，而不是產(chǎn)生異常
?? ?4，高效，存儲低，效率高?

算法時間效率度量

（1）可以忽略加法常數(shù)

O(2n + 3) = O(2n)
（2）與最高次項相乘的常數(shù)可忽略

O(2n^2) = O(n^2)
（3） 最高次項的指數(shù)大的，函數(shù)隨著 n 的增長，結果也會變得增長得更快

O(n^3) > O(n^2)
（4）判斷一個算法的（時間）效率時，函數(shù)中常數(shù)和其他次要項常?？梢院雎?#xff0c;而更應該關注主項（最高階項）的階數(shù)

O(2n^2) = O(n^2+3n+1)
O(n^3) > O(n^2
?

算法時間復雜度
?? ?

也就是執(zhí)行這個算法所花時間的度量
?? ?n ?1 ?= O(n) ? O(1)
?? ?

推到時間復雜度
?? ???

?1，用常數(shù)1 取代運行時間中的所有加法常數(shù)

? 2，在修改后的運行函數(shù)中，只保留最高階項。

? 3，如果最高階存在且不是1，則取除這個項相乘的常數(shù)。
?? ??? ?

3.舉例：

1. int i,j;

2. for ( i = 0; i < n; ++i){

3. for(j = i; j < n; ++j){

4. /*時間復雜度為 O(1) 的程序步驟序列 */

5. }

6. }

?? ???

?for(i=0;i<n;i++)
?? ??? ?{
?? ??? ??? ?i=5*i;
?? ??? ?}
?? ??? ?
?? ??? ?for()n
?? ??? ?{
?? ??? ??? ?for()n
?? ??? ?}
?? ??? ?O(1)<O(logn)<O(N)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
?? ??? ?
?? ??? ?
?? ??? ?
?? ??? ?for(int i = 0 ;i<100; i = *5)
?? ??? ?{
?? ??? ??? ?
?? ??? ?}

線性表

一.定義

?零個或多個數(shù)據(jù)元素的有限序列
?? ?元素之間是有順序了。如果存在多個元素，第一個元素無前驅，最有一個沒有后繼，其他的元素只有一個前驅和一個后繼。
?? ?當線性表元素的個數(shù)n（n>=0）定義為線性表的長度，當n=0時，為空表。在非空的表中每個元素都有一個確定的位置，如果a1是第一個元素，那么an就是第n個元素。
?? ?
線性表的常規(guī)操作 ?ADT
?

typedef struct?? ?person {
?? ?char name[32];
?? ?char sex;
?? ?int age;
?? ?int score;
}DATATYPE;

typedef int Datatype;

typedef struct list {
?? ?DATATYPE *head;
?? ?int tlen;
?? ?int clen;
}SeqList;

1.?SeqList *CreateSeqList(int len);

• 功能：創(chuàng)建一個長度為len的順序表。
• 實現(xiàn)思路：
  • 動態(tài)分配一個足夠大的內(nèi)存空間（通常是len個元素加上一個可能的頭部或尾部用于管理信息，如記錄當前長度）。
  • 初始化順序表的長度、容量等信息。
  • 返回指向新創(chuàng)建的順序表的指針。

2.?int DestroySeqList(SeqList *list);

• 功能：銷毀順序表，釋放其占用的內(nèi)存。
• 實現(xiàn)思路：
  • 釋放順序表所占用的內(nèi)存。
  • 將指針置為NULL，避免野指針問題。
  • 返回成功或失敗的狀態(tài)碼。

3.?int ShowSeqList(SeqList *list);

• 功能：顯示順序表中的所有元素。
• 實現(xiàn)思路：
  • 遍歷順序表，依次打印每個元素。
  • 返回成功或失敗的狀態(tài)碼（通常是成功）。

4.?int InsertTailSeqList(SeqList *list, DATATYPE data);

• 功能：在順序表的尾部插入一個元素。
• 實現(xiàn)思路：
  • 檢查順序表是否已滿。
  • 如果未滿，將新元素插入到順序表的末尾，并更新長度信息。
  • 如果已滿，可能需要擴容。
  • 返回成功或失敗的狀態(tài)碼。

5.?int IsFullSeqList(SeqList *list);

• 功能：判斷順序表是否已滿。
• 實現(xiàn)思路：
  • 比較順序表的當前長度與容量。
  • 如果長度等于容量，返回true（或1），否則返回false（或0）。

6.?int IsEmptySeqList(SeqList *list);

• 功能：判斷順序表是否為空。
• 實現(xiàn)思路：
  • 檢查順序表的當前長度是否為0。
  • 如果是，返回true（或1），否則返回false（或0）。

7.?int InsertPosSeqList(SeqList *list, DATATYPE data, int pos);

• 功能：在順序表的指定位置pos插入一個元素。
• 實現(xiàn)思路：
  • 檢查位置pos是否有效（即在0到長度之間）。
  • 如果有效，將pos及其之后的所有元素向后移動一位，為新元素騰出空間。
  • 在pos位置插入新元素，并更新長度信息。
  • 如果順序表已滿，可能需要擴容。
  • 返回成功或失敗的狀態(tài)碼。

8.?int FindSeqList(SeqList *list, char *name);

• 注意：這里假設順序表存儲的是某種具有名稱的對象，且DATATYPE可能不是直接相關的。這個函數(shù)的具體實現(xiàn)取決于SeqList和DATATYPE的具體定義。
• 功能：在順序表中查找具有指定名稱的元素。
• 實現(xiàn)思路：
  • 遍歷順序表，檢查每個元素的名稱是否與name匹配。
  • 如果找到匹配項，返回其位置（或某種表示找到的信息）。
  • 如果遍歷結束仍未找到，返回未找到的信息。

9.?int ModifySeqList(SeqList *list, char *old, DATATYPE new);

• 注意：與FindSeqList類似，這里也假設順序表存儲的是具有名稱的對象。
• 功能：將順序表中名稱與old匹配的元素替換為新的值new。
• 實現(xiàn)思路：
  • 遍歷順序表，找到名稱與old匹配的元素。
  • 如果找到，將其替換為new。
  • 返回成功或失敗的狀態(tài)碼（或修改的元素數(shù)量）。

10.?int DeleteSeqList(SeqList *list, char *name);

• 功能：從順序表中刪除名稱與name匹配的元素。
• 實現(xiàn)思路：
  • 遍歷順序表，找到名稱與name匹配的元素。
  • 如果找到，將該元素之后的所有元素向前移動一位，以覆蓋被刪除的元素。
  • 更新順序表的長度信息。
  • 返回成功

11.清楚順序表。

示例代碼：

sqelist.h

#ifndef SEQLIST_H
#define SEQLIST_Htypedef struct{char name[32];char sex;int age;int score;
}DATATYPE;
//typedef int Datatype;
typedef struct list {DATATYPE *head;int tlen;int clen;
}SeqList;SeqList* CreateSeqList(int size);
int DestroySeqList(SeqList*sl);
int InsertTailSeqList(SeqList *list, DATATYPE *data);
int IsFullSeqList(SeqList *list);
int IsEmptySeqList(SeqList *list);
int ShowSeqList(SeqList* list);
int GetSizeSeqList(SeqList* list);
int FindSeqList(SeqList *list, char *name);
DATATYPE* GetSeqListItem(SeqList *list,int ind);
int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos);
int ModifySeqList(SeqList *list, char *old, DATATYPE *newdata);
int DeleteSeqList(SeqList *list, char *name);
int ClearSeqList(SeqList *list);
#endif // SEQLIST_H

seqlist.c

#include "seqlist.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
SeqList *CreateSeqList(int size)
{if(size<=0){fprintf(stderr,"size is error,range >1");return NULL;}SeqList* sl = ( SeqList*)malloc(sizeof(SeqList));if(NULL == sl){perror("CreateSeqList malloc");exit(1);}sl->head = (DATATYPE*)malloc(sizeof(DATATYPE)*size);if(NULL == sl->head){perror("CreateSeqList malloc");exit(1);}sl->tlen = size;sl->clen = 0;return sl;
}int DestroySeqList(SeqList *sl)
{if(NULL == sl){fprintf(stderr,"SeqList point not NULL");return 1;}if(sl->head)free(sl->head);free(sl);return 0;
}int InsertTailSeqList(SeqList *list, DATATYPE *data)
{if(NULL == list){fprintf(stderr,"InsertTailSeqList error,list is null\n");return -1;}if(IsFullSeqList(list)){fprintf(stderr,"InsertTailSeqList error ,seqlist is full\n");return 1;}//list->head[list->clen] = *data;memcpy(&list->head[list->clen] , data,sizeof(DATATYPE));list->clen++;return 0;
}int IsFullSeqList(SeqList *list)
{if(NULL == list){fprintf(stderr,"IsFullSeqList error,list is null\n");return -1;}return list->clen == list->tlen;
}int IsEmptySeqList(SeqList *list)
{return 0==list->clen;
}int ShowSeqList(SeqList *list)
{if(NULL == list){fprintf(stderr,"list error,list is null\n");return -1;}int i = 0 ;int len = GetSizeSeqList(list);for(i=0;i<len;i++){printf("name:%s sex:%c age:%d score:%d\n",list->head[i].name,list->head[i].sex,list->head[i].age,list->head[i].score);}return 0;
}int GetSizeSeqList(SeqList *list)
{if(NULL == list){fprintf(stderr,"GetSizeSeqList error,list is null\n");return -1;}return list->clen;
}int FindSeqList(SeqList *list, char *name)
{if(NULL == list){fprintf(stderr,"FindSeqList error,list is null\n");return 1;}if(IsEmptySeqList(list)){fprintf(stderr,"FindSeqList error,seqlist is empty\n");return -1;}int len = GetSizeSeqList(list);int i = 0 ;for(i=0;i<len;i++){if(0==strcmp(list->head[i].name,name)){return i;}}return -1;}DATATYPE *GetSeqListItem(SeqList *list, int ind)
{if(NULL == list){fprintf(stderr,"seqlist is NULL\n");return NULL;}if(ind<0 || ind>GetSizeSeqList(list)){fprintf(stderr,"index is error . range>0  && <size\n");return NULL;}return &list->head[ind];
}int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos)
{if(NULL == list){fprintf(stderr,"list is null\n");return 1;}if(IsFullSeqList(list)){fprintf(stderr,"list is full\n");return 1;}if(pos<0 ||pos>GetSizeSeqList(list)){fprintf(stderr,"pos is error\n");return 1;}int i = 0 ;for(i =GetSizeSeqList(list); i>=pos ; i-- ){memcpy(&list->head[i],&list->head[i-1],sizeof(DATATYPE));}memcpy(&list->head[pos],data,sizeof(DATATYPE));list->clen++;return 0;
}int ModifySeqList(SeqList *list, char *old, DATATYPE *newdata)
{if(NULL == list){fprintf(stderr,"ModifySeqList error,list is null\n");return 1;}int ret = FindSeqList(list,old);if(-1 == ret){fprintf(stderr,"modify error,can't find\n");return 1;}DATATYPE* tmp = GetSeqListItem(list,ret);memcpy(tmp,newdata,sizeof(DATATYPE));return 0;
}int DeleteSeqList(SeqList *list, char *name)
{if(NULL == list){fprintf(stderr,"DeleteSeqList error,list is null\n");return 1;}int ret = FindSeqList(list,name);if(-1 == ret){return 1;}else{int i = 0 ;for(i =ret; i <GetSizeSeqList(list)-1 ; i++){memcpy(&list->head[i] ,&list->head[i+1],sizeof(DATATYPE));}}list->clen--;return 0 ;
}int CleanSeqList(SeqList *list)
{if(NULL == list){fprintf(stderr,"CleanSeqList error,list is null\n");return 1;}list->clen = 0 ;return 0;}

main.c

#include <stdio.h>
#include "seqlist.h"
int main()
{SeqList* sl = CreateSeqList(10);DATATYPE data[5]={{"zhangsan",'m',20,70},{"lisi",'f',21,60},{"wangmazi",'m',25,80},{"liubei",'f',30,85},{"caocao",'f',40,90},};InsertTailSeqList(sl,&data[0]);InsertTailSeqList(sl,&data[1]);InsertTailSeqList(sl,&data[2]);ShowSeqList(sl);//    char find_name[50]="li1si";//    int ret = FindSeqList(sl,find_name);//    if(-1 == ret)//    {//        printf("can't find person ,%s\n",find_name);//    }//    else//    {//       DATATYPE* tmp   =  GetSeqListItem(sl,ret) ;//       printf("name:%s score:%d\n",tmp->name,tmp->score);//    }printf("----------------pos------------------\n");InsertPosSeqList(sl,&data[3],3);ShowSeqList(sl);printf("----------------modify------------------\n");ModifySeqList(sl,"li1si",&data[4]);ShowSeqList(sl);printf("----------------del------------------\n");DeleteSeqList(sl,"lisi");ShowSeqList(sl);DestroySeqList(sl);printf("Hello World!\n");return 0;
}

內(nèi)存泄露檢測工具
sudo apt-get install valgrind
valgrind ./all

char buf[1024];

練習：

1.把dict.txt 內(nèi)容放到順序表中。
提供查詢功能。找到了，顯示意思。
如果沒找到，顯示輸入錯誤。
#quit ，退出程序。

dict.h

#ifndef DICT_H
#define DICT_Htypedef struct
{char word[20];char meaning[1022];int ret;
}MSG;typedef struct list
{MSG *head;int tlen;int clen;
}SeqList;SeqList* CreateSeqList(int size);
int DestroySeqList(SeqList *sl);
int InsertTailSeqList(SeqList *list, MSG*data);
int IsFullSeqList(SeqList *list);
int IsEmptySeqList(SeqList *list);
int ShowSeqList(SeqList* list);
int GetSizeSeqList(SeqList* list);
int FindSeqList(SeqList *list, char *name);
MSG* GetSeqListItem(SeqList *list,int ind);#endif // DICT_H

dict.c

#include "dict.h"
#include <stdio.h>
#include<string.h>
#include<stdlib.h>SeqList *CreateSeqList(int size)
{if(size<=0){fprintf(stderr,"size is error,range >1");return NULL;}SeqList* sl = ( SeqList*)malloc(sizeof(SeqList));if(NULL == sl){perror("CreateSeqList malloc");exit(1);}sl->head = (MSG*)malloc(sizeof(MSG)*size);if(NULL == sl->head){perror("CreateSeqList malloc");exit(1);}sl->tlen = size;sl->clen = 0;return sl;
}int DestroySeqList(SeqList *sl)
{if(NULL == sl){fprintf(stderr,"SeqList point not NULL");return 1;}if(sl->head)free(sl->head);free(sl);return 0;
}int InsertTailSeqList(SeqList *list, MSG*msg)
{if(IsFullSeqList(list)){fprintf(stderr,"InsertTailSeqlist error,seqlist is full\n");return -1;}memcpy(&list->head[list->clen],msg,sizeof(MSG));list->clen++;return 0;
}
int IsFullSeqList(SeqList *list)
{return list->clen == list->tlen;
}int IsEmptySeqList(SeqList *list)
{return 0==list->clen;
}
int GetSizeSeqList(SeqList *list)
{return list->clen;
}int FindSeqList(SeqList *list, char *word)
{if(IsEmptySeqList(list)){fprintf(stderr,"FindSeqList error,seqlist is empty\n");return -1;}int len = GetSizeSeqList(list);int i = 0 ;for(i=0;i<len;i++){if(0==strcmp(list->head[i].word,word))
{return i;}}return -1;}
MSG *GetSeqListItem(SeqList *list, int ind)
{if(NULL == list){fprintf(stderr,"seqlist is NULL\n");return NULL;}if(ind<0 || ind>GetSizeSeqList(list)){fprintf(stderr,"index is error . range>0  && <size\n");return NULL;}return &list->head[ind];
}

main.c

#include <stdio.h>
#include <string.h>
#include "dict.h"
#include <fcntl.h>
#include <stdlib.h>
int main()
{SeqList* sl = CreateSeqList(20000);MSG msg[2000];FILE *fp=fopen("/home/linux/cpz/dict.txt","r");if(NULL==fp){perror(" ");exit(1);}while(1){bzero(&msg,sizeof(msg));int i=0;char buf[1024]={0};if(NULL==fgets(buf,sizeof(buf),fp)){break;}char *word = NULL;char *mean = NULL;word=strtok(buf," ");mean=strtok(NULL,"\r");strcpy(msg[i].word,word);strcpy(msg[i].meaning,mean);InsertTailSeqList(sl,&msg[i]);}while(1){char find_word[50]={0};fgets(find_word,sizeof(find_word),stdin);find_word[strlen(find_word)-1]='\0';if(0==strcmp(find_word,"#quilt")){break;}int ret = FindSeqList(sl,find_word);if(-1 == ret){printf("can't find word ,%s\n",find_word);}else{MSG* tmp   =  GetSeqListItem(sl,ret) ;printf("word:%s mean:%s\n",tmp->word,tmp->meaning);}
}printf("Hello World!\n");return 0;
}

線性表順序存儲的優(yōu)點，缺點

優(yōu)點
?? ?1，無需為表中的邏輯關系增加額外的存儲空間
?? ?2，可以快速隨機訪問元素O(1)
缺點
?? ?1，插入，刪除元素需要移動元素o(n)
?? ?2，無法動態(tài)存儲。

優(yōu)點：
?

隨機訪問：順序表支持隨機訪問，即可以通過下標快速訪問表中的任意元素，訪問時間復雜度為O(1)。
存儲密度高：順序表在物理存儲上是連續(xù)的，因此它的存儲密度高，不會出現(xiàn)為了存儲數(shù)據(jù)元素而額外申請大量空間的情況（相較于鏈表等數(shù)據(jù)結構）。
空間利用率高：在順序表擴容之前，其空間是固定的，這有助于減少空間碎片，提高空間利用率。
易于實現(xiàn)：順序表的基本操作（如插入、刪除、查找等）相對簡單，易于理解和實現(xiàn)。

缺點：

插入和刪除操作成本高：當在順序表中進行插入或刪除操作時，可能需要移動大量的元素以保持順序表的連續(xù)性，特別是在表的前端或中間位置進行操作時，時間復雜度較高，最壞情況下為O(n)。
空間分配問題：順序表在初始化時需要預先分配一定大小的存儲空間，如果預估不準確，可能會導致空間浪費（分配過多）或溢出（分配不足）。雖然可以通過動態(tài)擴容來解決溢出問題，但每次擴容都需要重新分配內(nèi)存并復制數(shù)據(jù)，增加了時間成本。
擴容問題：當順序表需要擴容時，雖然可以動態(tài)申請更大的內(nèi)存空間，但這個過程涉及到舊數(shù)據(jù)的復制和新空間的申請，可能會影響到程序的性能。
表的大小固定：雖然可以通過動態(tài)擴容來解決表大小固定的問題，但在某些場景下，如果需要存儲的數(shù)據(jù)量非常大，而內(nèi)存空間有限，那么順序表可能就不是一個很好的選擇。