Part 1.順序表的代碼

一.順序表的內存申請

head.h:
typedef int datatype;typedef struct sqlist
{//數據元素datatype data[MAXSIZE];//順序表長度int len;}*sqlist;
//*sqlist的作用:
//sqlist:struct Sqlist *
sqlist create();head.c:
sqlist create()
{sqlist list =(sqlist)malloc(sizeof(struct sqlist));//申請堆區空間由指針list接收if(NULL == list)return NULL;//數據表元素清零bzero(list->data,sizeof(list->data));//順序表長度清零list->len = 0;return list;
}main.c:
sqlist list = create();

二.順序表尾插+遍歷

head.h:
int output(sqlist list);
int insert(sqlist list,datatype element);head.c:
//插入函數
int insert (sqlist list,datatype element)
{if(NULL == list || list->len == MAXSIZE){	printf("順序表滿了\n");return Faluse;}//插入數據list->data[list->len] = element;//順序表長度自增list->len++;return Success;
}
//遍歷函數
int output(sqlist list)
{if(NULL == list || list->len == 0){	printf("順序表為空\n");return Faluse;}for(int i = 0;i < list->len; i++){printf("%d\t",list->data[i]);}printf("\n");return Success;
}main.c：
for(int i = 0; i < MAXSIZE; i++){scanf("%d",&element);insert(list,element);}output(list);

三.順序表尾刪

head.h:
int delete_rear(sqlist list);head.c:
int delete_rear(sqlist list)
{if(NULL == list || list->len == 0){	printf("順序表為空\n");return Faluse;}list->len--;return Success;
}main.c:
delete_rear(list);

四.順序表按下表插入

head.h:
int index_insert(sqlist list,int index, datatype element);head.c:
int index_insert(sqlist list,int index, datatype element)
{if(NULL == list || list->len == MAXSIZE || index < 0 || index >= list->len){	printf("error\n");return Faluse;}list->len++;for (int i = list->len; i >index; i--)//將要加數的下標的表值都往后移{list->data[i] = list->data[i-1];}list->data[index] = element;return Success;
}main.c:
index_insert(list,1,9);

五.順序表按下表刪除

head.h:
int index_delete(sqlist list,int index);head.c:
int index_delete(sqlist list,int index)
{if(NULL == list || list->len == 0 || index < 0 || index >= list->len){	printf("error\n");return Faluse;}for (int i = index; i < list->len; i++)//全部前移{list->data[i] = list->data[i+1];}list->len--;return Success;
}main.c：
index_delete(list,2);

六.順序表按下表修改

head.h:
int index_change(sqlist list,int index,datatype element);head.c:
int index_change(sqlist list,int index, datatype element)
{if(NULL == list || list->len == 0 || index < 0 || index >= list->len){	printf("error\n");return Faluse;}list->data[index] = element;//將下標對應的表值改為輸入的值return Success;
}main.c:
index_change(list,2,5);

七.順序表按下表查找

head.h:
int index_select(sqlist list,int index);head.c:
int index_select(sqlist list,int index)
{if(NULL == list || list->len == 0 || index < 0 || index >= list->len){	printf("error\n");return Faluse;}printf("%d\n",list->data[index]);//輸出下標的值return Success;
}main.c:
index_select(list,3);

八.順序表按元素刪除

head.h:
int element_delete(sqlist list,datatype element);head.c:
int element_delete(sqlist list,datatype element)
{if(NULL == list || list->len == 0){	printf("error\n");return Faluse;}int index = 0;for(int j = 0; j < list->len; j++){if(list->data[j] == element)//找到對應值的下標，進行下標刪除{index = j;	for(int i = index; i < list->len; i++){list->data[i] = list->data[i+1];}list->len--;}}return Success;
}main.c；
element_delete(list,5);

九.順序表按元素查找

head.h:
int element_select(sqlist list,datatype element);head.c:
int element_select(sqlist list,datatype element)
{if(NULL == list || list->len == 0){	printf("error\n");return Faluse;}int index = 0;for(int j = 0; j < list->len; j++){if(list->data[j] == element)//找到對應元素下標并輸出{printf("%d\n",j);}}return Success;
}main.c：
element_select(list,9);

十.順序表按元素修

head.h:
int element_change(sqlist list,datatype element,datatype elementchange);head.c:
int element_change(sqlist list,datatype element,datatype elementchange)
{if(NULL == list || list->len == 0){	printf("error\n");return Faluse;}int index = 0;for(int j = 0; j < list->len; j++){if(list->data[j] == element)//循環尋找下標，并賦值{list->data[j] = elementchange;}}return Success;
}main.c：
element_change(list,9,5);

十一.順序表去重

head.h:
int D_repetition_rate(sqlist list);head.c:
int D_repetition_rate(sqlist list)
{if(NULL == list || list->len == 0){	printf("error\n");return Faluse;}int index = 0;for(int i = 0; i < list->len; i++){for(int j = i + 1; j < list->len; j++)//每次循環與循環首進行比較{if(list->data[i] == list->data[j])//找到相同的值，調用下標刪除{	index = j;	for(int i = index; i < list->len; i++){list->data[i] = list->data[i+1];}list->len--;j--;//往前走一位}}}return Success;
}main.c：
D_repetition_rate(list);

十二.順序表排序

head.h:
int paixu(sqlist list);head.c:
int paixu(sqlist list)
{if(NULL == list || list->len == 0){	printf("error\n");return Faluse;}for(int i = 1; i < list->len; i++)//冒泡排序{for(int j = 0; j < list->len-i; j++){if(list->data[j] >= list->data[j+1]){		int x = list->data[j];list->data[j] = list->data[j+1];list->data[j+1] = x;}}}return Success;
}main.c：
paixu(list);

Part 2.整理

一.數據結構

? ? ? ? 1.邏輯結構

? ? ? ? ? ? ? ? a.集合結構

元素之間沒有關系

? ? ? ? ? ? ? ? b.線性結構

元素之間有一對一的關系

? ? ? ? ? ? ? ? c.樹形結構

元素之間有一對多關系

? ? ? ? ? ? ? ? d.圖形結構

元素之間有多對多的關系

? ? ? ? 2.存儲結構

? ? ? ? ? ? ? ? a.順序存儲

使用一段連續的空間存儲多個相同類型的數據元素

? ? ? ? ? ? ? ? b.鏈式存儲

使用任意一段空間存儲多個相同類型的數據元素

? ? ? ? ? ? ? ? a和b的區別

兩種方式都是邏輯上相連，但是鏈式存儲物理空間上沒有相連

? ? ? ? ? ? ? ? c.索引結構

用索引方法和數據表實現查找的結構

? ? ? ? ? ? ? ? d.散列存儲

使用哈希存儲的一直存儲方式

? 二.時間復雜度

T(n) = O(f(n))

T：時間

n：問題的規模

O：大O階，漸進符

無循環函數

int a = 0;? ? ? ? ? ? ? ? 1

printf("%d",a);? ? ? ? ? ? ? ? 1

T(n) =O(1)? ? ? ? ? ? ? ??

for循環

for(int i? = 0; i<n; i++)? ? ? ? ? ? ? ? n+1

{

? ? ? ??printf("%d",i);? ? ? ? ? ? ? ? n

}

T(n) =O(n)

嵌套for循環

for(int i? = 0; i<n; i++)? ? ? ? ? ? ? ? n+1

{

? ? ? ??for(int j? = 0; j<n; j++)? ? ? ? ?n*(n+1)

????????{

????????????????printf("%d",i);? ? ? ? ? ?n*n

????????}? ? ? ? ??

}

T(n) =O(n^2)

三.順序表

? ? ? ? 1.本質

一個下標從0開始，和數組相似的，連續存儲的空間

? ?

????????