二:各個主要函數
一:CreatSeqList
SeqList *CreateSeqList(int len);
-------------------------------------------------------------/*** @brief Create a Seq List object 創建一個順序表** @param n 是順序表的大小* @return SeqList* 指向順序表的指針 (重要) ,錯誤的話返回NULL*/
SeqList *CreateSeqList(int n)
{SeqList *sl = malloc(sizeof(SeqList));if (sl == NULL){fprintf(stderr,"CreateSeqList malloc error\n"); // strerr 專門輸出錯誤信息的return NULL;}sl->head = malloc(sizeof(DATATYPE) * n);if (NULL == sl->head){fprintf(stderr,"CreateSeqList malloc2 error\n"); // strerr 專門輸出錯誤信息的return NULL;}sl->tlen = n;sl->clen = 0;return sl;
}
作用:創建一個順序表,最多可存儲 len
個元素。
返回值:創建好的順序表指針。
二:DestroySeqList
`int DestroySeqList(SeqList *list);`
作用:銷毀順序表,釋放所有內存
三:ShowSeqList
int ShowSeqList(SeqList *list);
作用:遍歷順序表,將所有元素打印出來
四:InsertTailSeqList
int InsertTailSeqList(SeqList *list, DATATYPE data);
作用:將一個元素插入到順序表末尾。
五:IsFullSeqList
int IsFullSeqList(SeqList *list);
作用:判斷順序表是否已滿
返回值:
1
表示已滿。0
表示未滿。
六:IsEmptySeqList
int IsEmptySeqList(SeqList *list);
--------------------------------------------------------
int IsEmptySeqList(SeqList* sl)
{return 0 == sl->clen;
}
作用:判斷順序表是否為空。
返回值:
1
表示為空。0
表示非空。
七:InsertPosSeqList
int InsertPosSeqList(SeqList *list, DATATYPE data, int pos);
作用:將一個元素插入到指定位置 pos
。
關鍵點:
- 判斷是否滿。
- 判斷位置是否有效。
- 從尾部開始向后移動,騰出空間。
- 插入元素到
pos
。 len++
。
八:FindSeqList
int FindSeqList(SeqList *list, char *name);
---------------------------------------------
作用:在順序表中查找名字為 name
的元素
返回值:
- 找到則返回該元素的索引(下標)。
- 未找到返回
-1
。
九:ModifySeqList
int ModifySeqList(SeqList *list, char *old, DATATYPE new);
作用:將名字為 old
的元素替換為 new
。
流程:
- 調用
FindSeqList
查找舊元素。 - 替換內容。
十:DeleteSeqList
int DeleteSeqList(SeqList *list, char *name);
作用:刪除名字為 name
的元素。
流程:
- 找到該元素的下標。
- 用后面的元素依次向前覆蓋。
len--
。
十一:ClearSeqList
int ClearSeqList(SeqList *list);
作用:清空順序表中所有元素,但不釋放內存。
等效于:list->len = 0;
三:線性表(升級版的數組)
一:基礎定義
1.線性表:零個或多個數據元素的有限序列
線性表元素的個數n(n≥0)定義為線性表的長度,當n=0時,稱為空表
線性表的數據對象集合為{a1,a2.....an)
,每個元素的類型均為DataType
。其中,除第一個元素a外,每一個元素有且只有一個直接前驅元素,除了最后一個元素a,外,每一個元素有且只有一個直接后繼元素。數據元素之間的關系是一對一的關系
? 元素之間是有順序了。如果存在多個元素,第一個元素無前驅,最有一個沒有后繼,其他的元素只有一個前驅和一個后繼。
? 當線性表元素的個數n(n>=0)定義為線性表的長度,當n=0時,為空表。在非空的表中每個元素都有一個確定的位置,如果a1是第一個元素,那么an就是第n個元素。
線性表順序存儲的優點,缺點
優點
1,無需為表中的邏輯關系增加額外的存儲空間
2,可以快速隨機訪問元素O(1)
缺點
1,插入,刪除元素需要移動元素o(n)
2,無法動態存儲。
二:線性表的順序存儲結構
1.為了建立一個線性表,要在內存中找一塊地,于是這塊地的第一個位置就非常關鍵,它是存儲空間的起始位置。
2.順序存儲結構需要三個屬性:存儲空間的起始位置:數組data
,它的存儲位置就是存儲空間的存儲位置。
? 線性表的最大存儲容量:數組長度MaxSize
。
? 線性表的當前長度:length。
三:memcpy()
void *memcpy(void *str1, const void *str2, size_t n)
參數:
- str1 – 指向用于存儲復制內容的目標數組,類型強制轉換為 void* 指針。
- str2 – 指向要復制的數據源,類型強制轉換為 void* 指針。
- n – 要被復制的字節數。
返回值:該函數返回一個指向目標存儲區 str1 的指針。
memcpy(&sl->head[sl->clen], data, sizeof(DATATYPE));
//練習InsertPosSeqList
//由于順序表的原因,當舊數據和clen一樣大時,無法插入新數據
//當舊數據比clen小至少2個數據時,新數據不能直接插入最后一位的位置
//當新數據插入舊數據時,且當舊數據比clen小至少1個數據時,
//新數據前的舊數據不變位置,新數據后的舊數據由于新數據的插入,向后順延一個數據的位置
四::順序表(Seqlist
)
1.組成
? Head
組頭:Head[0]—Head[1]--------------Head[n]·
? Tlen
:總長度
? Clen
:當前長度
DATATYPE * Head
理解:就是head,tlen,clne
三個組成結構體,其中clen
是我所設的數組a的長度大小(a[clen] = {...,.,.}
),其中tlen
就是所設數組a[clen] = {...,.,.}
中存放的有效元素個數,所以head
這個一位數組(指針變量)可以指向數組a[clen] = {...,.,.}
中存放的有效元素。clen
限制所設數組長度,tlen
存放有效元素個數,head
訪問有效元素,head
的長度應該<=clen
。
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 new);//修改
int DeleteSeqList(SeqList *list, char *name);//刪除
int ClearSeqList(SeqList *list);//清空表
//.h文件
#ifndef _SEQLIST_H_
#define _SEQLIST_H_typedef struct
{char name[32];char sex;int age;int score;}PER;typedef PER DATATYPE;
typedef struct
{DATATYPE * head; // 數組的數組名 存儲datatype 類型的數據int tlen; // 數組的容量int clen; // 數組中有效元素的個數
}SeqList;// 順序表 表頭結構SeqList* CreateSeqList(int n);
int InsertTailSeqList(SeqList* sl,DATATYPE*data);
int ShowSeqList(SeqList* sl);
int IsFullSeqList(SeqList* sl);
int GetSizeSeqList(SeqList* sl);
int InsertPosSeqList(SeqList *sl, DATATYPE *data, int pos);#endif
----------------------------------------------------------------------------------------------------------//.c文件
SeqList *CreateSeqList(int n)
{SeqList *sl = malloc(sizeof(SeqList));//malloc 是動態內存分配函數,用于在堆(Heap)上申請一塊連續的內存空間sizeof(SeqList) 計算 SeqList 結構體的大小(字節數),確保分配的內存足夠存儲整個結構體。//SeqList *sl:定義一個指向 SeqList 結構體的指針 sl。將 malloc 返回的內存地址賦值給 sl,此時 sl 指向新分配的內存空間。//直接定義 SeqList sl 會創建在棧(Stack)上,但順序表通常需要動態調整大小(如擴容),因此需通過堆內存動態分配。if (NULL == sl){fprintf(stderr,"CreateSeqList malloc error\n"); // strerr 專門輸出錯誤信息的return NULL;}sl->head = malloc(sizeof(DATATYPE) * n);if (NULL == sl->head){fprintf(stderr,"CreateSeqList malloc2 error\n"); // strerr 專門輸出錯誤信息的return NULL;}sl->tlen = n;sl->clen = 0;return sl;
}
/*** @brief 順序表的尾插** @param sl 被插入的 順序表* @param data 被存儲的數據的指針* @return int 0表示成功 1 表示失敗*/
int InsertTailSeqList(SeqList *sl, DATATYPE *data)
{if (IsFullSeqList(sl)){return 1;}// strcpymemcpy(&sl->head[sl->clen], data, sizeof(DATATYPE));sl->clen++;return 0;
}int InsertPosSeqList(SeqList *sl, DATATYPE *data, int pos)
{if (sl == NULL || data == NULL){fprintf(stderr, "Error: NULL pointer!\n");return -1; // 返回錯誤碼}if (sl->clen >= sl->tlen){fprintf(stderr, "Error: SeqList is full!\n");return -1;}if (pos > sl->clen || pos < 0){fprintf(stderr,"CreateSeqList malloc2 error\n"); // strerr 專門輸出錯誤信息的}if (pos < sl->clen){for (int i = sl->clen; i > pos; i--){memcpy(&sl->head[i], &sl->head[i - 1], sizeof(DATATYPE));}}memcpy(&sl->head[pos], data, sizeof(DATATYPE));sl->clen++;return 0;
}
/*** @brief 遍歷整個順序表** @param sl 被遍歷的順序表的指針* @return int 0表示成功 1 表示失敗*/
int ShowSeqList(SeqList *sl)
{int size = GetSizeSeqList(sl);int i = 0;for (i = 0; i < size; i++){printf("name:%s sex:%c age:%d score:%d\n", sl->head[i].name,sl->head[i].sex, sl->head[i].age, sl->head[i].score);}return 0;
}int IsFullSeqList(SeqList *sl) { return sl->clen == sl->tlen; }
int GetSizeSeqList(SeqList *sl) { return sl->clen; }
4-1:完整seqlist
練習
//.h文件#ifndef _SEQLIST_H_
#define _SEQLIST_H_typedef struct
{char name[32];char sex;int age;int score;}PER;typedef PER DATATYPE;
typedef struct
{DATATYPE * head; // 數組的數組名 存儲datatype 類型的數據int tlen; // 數組的容量int clen; // 數組中有效元素的個數
}SeqList;// 順序表 表頭結構SeqList* CreateSeqList(int n);
int InsertTailSeqList(SeqList* sl,DATATYPE*data);
int ShowSeqList(SeqList* sl);
int IsFullSeqList(SeqList* sl);
int GetSizeSeqList(SeqList* sl);
int InsertPosSeqList(SeqList* sl,DATATYPE*data,int pos);
int IsEmptySeqList(SeqList* sl);
int FindSeqListByName(SeqList *ls, char *name);
DATATYPE* GetItemSeqList(SeqList* sl,int pos);
int ClearSeqList(SeqList *sl);
int ModifySeqList(SeqList *sl, char *old, DATATYPE*data);
int DeleteSeqList(SeqList *sl, char *name);
int DestroySeqList(SeqList *sl);
#endif
-----------------------------------------------------------------
//.c文件
#include "seqlist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*** @brief Create a Seq List object 創建一個順序表** @param n 是順序表的大小* @return SeqList* 指向順序表的指針 (重要) ,錯誤的話返回NULL*/
SeqList *CreateSeqList(int n)
{SeqList *sl = malloc(sizeof(SeqList));if (NULL == sl){fprintf(stderr,"CreateSeqList malloc error\n"); // strerr 專門輸出錯誤信息的return NULL;}sl->head = malloc(sizeof(DATATYPE) * n);if (NULL == sl->head){fprintf(stderr,"CreateSeqList malloc2 error\n"); // strerr 專門輸出錯誤信息的return NULL;}sl->tlen = n;sl->clen = 0;return sl;
}
/*** @brief 順序表的尾插** @param sl 被插入的 順序表* @param data 被存儲的數據的指針* @return int 0表示成功 1 表示失敗*/
int InsertTailSeqList(SeqList *sl, DATATYPE *data)
{if (IsFullSeqList(sl)){return 1;}// strcpymemcpy(&sl->head[sl->clen], data, sizeof(DATATYPE));sl->clen++;return 0;
}
/*** @brief 遍歷整個順序表** @param sl 被遍歷的順序表的指針* @return int 0表示成功 1 表示失敗*/
int ShowSeqList(SeqList *sl)
{int size = GetSizeSeqList(sl);int i = 0;for (i = 0; i < size; i++){printf("name:%s sex:%c age:%d score:%d\n", sl->head[i].name,sl->head[i].sex, sl->head[i].age, sl->head[i].score);}return 0;
}int IsFullSeqList(SeqList *sl) { return sl->clen == sl->tlen; }
int GetSizeSeqList(SeqList *sl) { return sl->clen; }int InsertPosSeqList(SeqList *sl, DATATYPE *data, int pos)
{int size = GetSizeSeqList(sl);if (pos < 0 || pos > size){fprintf(stderr,"CreateSeqList malloc2 error\n"); // strerr 專門輸出錯誤信息的return 1;}if (IsFullSeqList(sl)){printf("seqlist full\n");return 1;}int i = 0;for (i = sl->clen; i > pos; i--){memcpy(&sl->head[i], &sl->head[i-1], sizeof(DATATYPE));}memcpy(&sl->head[pos], data, sizeof(DATATYPE));sl->clen++;return 0;
}
int IsEmptySeqList(SeqList* sl)
{return 0 == sl->clen;//邏輯表達式,如果clen=0,返回1
}
/*** @brief 在順序表中按照名字查找信息* * @param ls * @param name * @return int -1沒找到*/
int FindSeqListByName(SeqList *sl, char *name)
{if(IsEmptySeqList(sl))//1執行{return -1;}int size = GetSizeSeqList(sl);int i = 0;for(i=0;i<size;i++){if(0 == strcmp(sl->head[i].name, name)){return i;}}return -1;
}
DATATYPE* GetItemSeqList(SeqList* sl,int pos)
{int size = GetSizeSeqList(sl);if(pos<0 || pos > size-1){return NULL;}return &sl->head[pos];
}
int ClearSeqList(SeqList *sl)
{sl->clen = 0; //本質上就是要新的數據直接覆蓋到舊數據的位置上,clen=0意味著舊數據無法寫入return 0;
}
int ModifySeqList(SeqList *sl, char *old, DATATYPE*data)
{int ret = FindSeqListByName(sl, old);if(-1 == ret){return 1;}memcpy(&sl->head[ret], data, sizeof(DATATYPE));return 0;
}
int DeleteSeqList(SeqList *sl, char *name)
{int ret = FindSeqListByName(sl, name);if(-1 == ret){return -1;}int i;int size = GetSizeSeqList(sl);for(i=ret;i<size;i++)//循環前移{memcpy(&sl->head[i], &sl->head[i+1], sizeof(DATATYPE));}sl->clen--;return 0;
}
int DestroySeqList(SeqList *sl)
{free(sl->head);free(sl);return 0;
}
五:makefile
1.規范名字 makefile/Makefile
//一般用第二個
a.out:main.c seqlist.c//目標:依賴gcc main.c seqlist.c -o a.out//規則clean:rm a.out--------------------------------------------------------
編寫完make再make clean
//形式1
#目標:依賴
#\t規則a.out:main.c seqlist.cgcc main.c seqlist.c -o a.out clean:rm a.out
//形式2
a.out:main.c seqlist.cgcc $^ -o $@//$@ 目標:上一條語句// $^ 依賴:只在這條規則生效
//形式3
SRC = main.c
SRC += seqlist.c//在上一套SRC追加'+='
DST = all
$(DST) : $(SRC)gcc $^ -o $@
clean:rm $(DST)
//形式4 適用于大型文件
SRC = main.o
SRC += seqlist.o
DST = all%.o:%.c //%代表文件名()通配符,是一個變量,對應的.c文件 生成對應的.o文件gcc -c $^ -o $@
$(DST) : $(SRC)gcc $^ -o $@
clean:rm $(DST) $(SRC)//也再刪.o文件
六:線性表的鏈式存儲
- 線性表鏈式存儲結構的特點是一組任意的存儲單位存儲線性表的數據元素,存儲單元可以是連續的,也可以不連續。可以被存儲在任意內存未被占用的位置上。
? 所以前面的順序表只需要存儲數據元素信息就可以了。在鏈式結構中還需要一個元素存儲下一個元素的地址。
? 為了表示每個數據元素,ai
與其直接后繼數據元素ai+1
之間的邏輯關系,對ai
來說,除了存儲其本身的信息外,還需要存一個指示器直接后續的信息。把存儲元素信息的域叫數據域,把存儲直接后繼位置的域叫指針域。這兩部分信息組成數據元素ai
的存儲映像,叫結點(Node
);
typedef struct
{char name[32];char sex;int age;int score;
}DATATYPE;
------------------------------------------------------------------------------------typedef struct node//必須有名字,不然無法表示引用自己
{DATATYPE data;struct node *next;
}LinkNode;typedef struct
{LinkNode *head;int clen;
}LinkList;
int InsertHeadLinkList(LinkList *list, DATATYPE *data)
{//新結點的初始化LinkNode *newnode = malloc(sizeof(LinkNode));if (NULL == newnode){fprintf(stderr, "InsertHeadLinkList malloc\n");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;// 把新節點連接到鏈表中if (IsEmptyLinkList(list)) // empty{list->head = newnode;}else{newnode->next = list->head;list->head = newnode;}list->clen++;return 0;
}