??基本概念
??一.線性表、順序表的定義
??(1)線性表:
是n個具有相同特性的數據元素的有限序列。線性表在邏輯上是線性結構,但在物理上存儲時,通常以數組和鏈式結構的形式存儲。
??(2)順序表:
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數據元素的線性結構,一般情況下采用數組存儲。在數組上完成數據的增刪查改。
??二.順序表的分類
??(1)靜態(tài)順序表:
1.概念:使用定長數組存儲元素
2.定義方法:數組使用方括號法,例如:
typedef struct
{
int age;
int height;
double weight;
}Student;
typedef struct
{
Student stu[100];//Student類型的數組
int length;//元素的有效個數
int listsize;//最多容納多少個元素
}SqList;
3.缺陷:方括號[ ]內只能是定值,一旦定義了大小就不可改變
??(2)動態(tài)順序表:
1.概念:使用動態(tài)開辟的數組存儲元素
2.定義方法:用指針指向數組,例如:
typedef struct
{
int age;
int height;
double weight;
}Student;
typedef struct
{
Student* stu;//Student類型的數組
int length;//元素的有效個數
int listsize;//最多容納多少個元素
}SqList;
3.相較于靜態(tài)順序表,動態(tài)順序表可以改變數組大小,更合理的利用空間
??動態(tài)順序表相關操作函數
為方便理解,以一個學生信息表為例。最開始先開辟5個結構體大小的位置,如果后面不夠則每次多開辟2個位置;學生信息由年齡、身高、體重3個數據組成。
??定義部分
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 5
#define INCREASE 2
typedef struct
{
int age;
int height;
double weight;
}Student;
typedef struct
{
Student* stu;//Student類型的數組
int length;//元素的有效個數
int listsize;//最多容納多少個元素
}SqList;
??一.初始化順序表
int InitList(SqList* L)
{
//1.申請空間
L->stu = (Student*)malloc(LIST_INIT_SIZE * sizeof(Student));
//2.判斷是否申請成功
if (!L->stu)
exit(-1);//exit(-1)表示退出程序
//3.如果拿到了內存空間,就初始化順序表
L->length = 0;
L->listsize = LIST_INIT_SIZE;
return 1;
}
步驟:
??1.用malloc申請空間
??2.判斷是否申請成功
補:exit和return的區(qū)別:exit(-1)表示終止程序,而return只是結束當下函數
??3.如果拿到了內存空間,就初始化順序表
length表示有效元素個數,目前為0;listsize表示數組當前最大容量,假設初始最大容量LIST_INIT_SIZE為5
??二.銷毀順序表
int DeleteList(SqList* L)
{
//1.判斷順序表是否存在
if (L->stu == NULL)//說明不存在
return 0;//不可以解引用NULL
//2.如果存在,則釋放對應的內存
free(L->stu);
L->stu = NULL;
//3.釋放內存后,恢復表的初始值
L->length = 0;
L->listsize = 0;
return 1;
}
步驟:
??1.判斷順序表是否存在
如果不存在,直接退出程序,沒必要進行后續(xù)操作
??2.如果存在,則釋放對應的內存
注:好習慣是只要用完free,就將指針置為NULL
??3.釋放內存后,恢復表的初始值
??三.輔助操作函數
以下兩個函數是增刪查改過程中頻繁用到的操作,為防止代碼冗余,將重復工作的代碼封裝成相應的兩個函數
??(1)元素復制函數(CopyValue)
//元素復制
void CopyValue(Student* s1, Student* s2)
{
s1->age = s2->age;
s1->height = s2->height;
s1->weight = s2->weight;
}
注:需要傳兩組數據的地址,因為形參的改變不影響實參
s1是元素復制后的位置,s2是元素復制前的位置
??(2)輸入信息函數(Print)
void Print(Student* onestu)
{
printf("請輸入:\n");
printf("年齡:");
scanf("%d", &onestu->age);
printf("身高:");
scanf("%d", &onestu->height);
printf("體重:");
scanf("%lf", &onestu->weight);
}
在首次大規(guī)模插入信息、插入單個信息、查找信息、改動信息等時候都需要輸入信息
??四.(增)擴大順序表長度
//擴大數組長度
void ExpandList(SqList* L)
{
//1.申請內存
Student* p = (Student*)realloc(L->stu, (L->listsize + INCREASE) * sizeof(Student));
//2.判斷是否申請成功
if (!p)
exit(-1);
//3.如果申請到了內存,更新順序表的信息(包括學生數組、最大容納學生量)
L->stu = p;
L->listsize += INCREASE;
}
步驟:
??1.申請內存
由于初始化時已經由malloc初次申請了部分空間,以后每次增加空間都是在初始基礎上增加,因此用realloc來擴大順序表。
??realloc使用時的注意事項:
①realloc的第二個參數不是增加了多少空間,而是要擴大至多大的空間,即整個大空間的大小
②用一個新的Student類型的指針接收realloc的返回值,當返回值不為NULL時再將值賦給指向數組的指針L->stu
??2.判斷是否申請成功
??3.如果申請到了內存,更新順序表的信息(包括學生數組位置、最大容納學生量)
??(1)對順序表大規(guī)模插入信息
int InsertValue(SqList* L, int n)
{
//1.確保有足夠空間存放信息
while (L->listsize < n)
{
ExpandList(L);
if (L->listsize >= n)
break;
}
//2.有足夠空間,開始插入信息
for (int i = 0;i < n;i++)
{
Print(&L->stu[i]);
printf("已成功增加一組信息\n");
L->length++;
}
return 1;
}
步驟:
1.確保有足夠空間存放信息
2.有足夠空間,開始插入信息
??(2)在順序表尾部插入元素
//在順序表尾部插入元素
void InsertLastList(SqList* L, Student* onestu)
{
//1.判斷數組滿沒滿,滿就擴大數組長度
if (L->length >= L->listsize)
ExpandList(L);
//2.有足夠空間,在尾部插入新元素(將新元素拷貝到數組末尾)
CopyValue(&L->stu[L->length], onestu);
//3.更新學生數量
L->length++;
}
第二個參數onestu是被插入的信息
步驟:
??1.判斷數組滿沒滿,滿就用ExpandList函數擴大數組長度。
??2.有足夠空間,在尾部插入新元素(將新元素拷貝到數組末尾)
??3.更新學生數量
??(3)在順序表頭部插入元素
//在順序表頭部插入元素
void InsertFirstList(SqList* L, Student* onestu)
{
//1.判斷數組滿沒滿,滿就擴大數組長度
if (L->length >= L->listsize)
ExpandList(L);
//2.有足夠空間,先將所有元素向后挪動1位,
// 從后往前挪,要不然會被覆蓋
for (int i = L->length-1;i>=0;i--)
{
CopyValue(&L->stu[i + 1], &L->stu[i]);
}
//3.將新元素拷貝到數組開頭
CopyValue(&L->stu[0], onestu);
//4.更新學生數量
L->length++;
}
第二個參數onestu是被插入的信息
步驟:
??1.判斷數組滿沒滿,滿就用ExpandList函數擴大數組長度。
??2.有足夠空間,先將所有元素向后挪動1位。
注:要從最后一個元素開始往前挪,如果從前往后挪的話,會將數組中的所有元素全部覆蓋成第一個元素。
??3.將新元素拷貝到數組開頭
??4.更新學生數量
??(4)在順序表指定位置插入元素
//在順序表指定位置插入元素
int InsertLocList(SqList* L, int i, Student* onestu)
{
//1.判斷位置是否合法
if (i < 0 || i >= L->length)
{
return 0;
}
//2.判斷數組是否有空位,沒有的話擴容
if (L->length == L->listsize)
{
ExpandList(L);
}
//3.將插入點及后面的元素向后移動1位
for (int j = L->length - 1;j >= i;j--)//j>=i+1
{
//注1:要從數組的最后一個元素依次向后挪動1位,如果從插入點
// 開始挪動的話,數組原先的內容會被覆蓋
//注2:j必須要能等于i,因為i是插入點,要連同插入點往后挪1位
CopyValue(&L->stu[j + 1], &L->stu[j]);
}
//4.插入元素
CopyValue(&L->stu[i], onestu);
//5.更新表中的信息
L->length++;
return 1;
}
第二個參數onestu是被插入的信息
步驟:
??1.判斷位置是否合法
??2.判斷數組是否有空位,沒有的話擴容
??3.將插入點及后面的元素向后移動1位
注:
①要從數組的最后一個元素依次向后挪動1位,如果從插入點開始挪動的話,數組原先的內容會被覆蓋
②j必須要能等于i,因為i是插入點,要連同插入點往后挪1位
??4.插入元素
??5.更新表中的信息
??五.(刪)刪除順序表中的信息
void DropOneValue(SqList*L,Student* onestu4)
{
//1.判斷是否有該組數據
int ret = FindOneList(L, onestu4);
if (ret == -1)
{
printf("沒有該信息\n");
return;
}
//2.進行刪除
for (int i = ret + 1;i <= L->length - 1;i++)
{
CopyValue(&L->stu[i - 1], &L->stu[i]);
}
printf("刪除成功\n");
//3.成員數量信息變動
L->length--;
}
第二個參數onestu4是要被刪除的信息
步驟:
??1.判斷是否有該組數據
??2.有信息的話進行刪
將刪除點后面的所有元素向前挪動1位
??3.成員數量信息變動
??六.(查)查找順序表中的某個元素
int FindOneList(SqList* L, Student* onestu3)
{
int i = 0;
while (i < L->length)
{
if ((L->stu[i].age == onestu3->age)
&& (L->stu[i].height == onestu3->height)
&& (L->stu[i].weight == onestu3->weight))
return i;
i++;
}
return -1;
}
第二個參數onestu3是被查找的信息
??1.找到的話返回這個元素在數組中的下標;找不到的話返回-1(為什么不返回0,因為下標也有可能是0)
??2.需要增加一組Student類型的數據作為對照信息(你肯定要先告訴我你要找的人的信息我才能找到這個人存不存在、存在的話是幾號)
??七.(改)改變順序表中某元素信息
void ModifyOneValue(SqList* L, Student* onestu5, Student* onestu6)
{
//1.判斷該信息是否存在
int ret=FindOneList(L, onestu5);
if (ret == -1)
{
printf("沒有該信息\n");
return;
}
//2.信息存在,進行修改
printf("請輸入修改后信息:\n");
Print(onestu6);
CopyValue(&L->stu[ret], onestu6);
}
參數二onestu5是改變前的信息,第三個參數onestu6是改變后的信息
步驟:
??1.判斷該信息是否存在
??2.信息存在,進行修改
??八.遍歷順序表打印出所有元素
//遍歷順序表
void FindAllList(SqList* L)
{
int i = 0;
for (i = 0;i < L->length;i++)
{
printf("age=%d,height=%d,weight=%lf\n", L->stu[i].age,
L->stu[i].height, L->stu[i].weight);
}
}
??用動態(tài)順序表實現(xiàn)學生信息操作程序
(完整程序,連著的三部分)
??一.聲明與定義
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 5
#define INCREASE 2
typedef struct
{
int age;
int height;
double weight;
}Student;
typedef struct
{
Student* stu;//Student類型的數組
int length;//元素的有效個數
int listsize;//最多容納多少個元素
}SqList;
??二.被調用函數
//初始化順序表
int InitList(SqList* L)
{
//1.申請空間
L->stu = (Student*)malloc(LIST_INIT_SIZE * sizeof(Student));
//2.判斷是否申請成功
if (!L->stu)
exit(-1);//exit(-1)表示退出程序
//3.如果拿到了內存空間,就初始化順序表
L->length = 0;
L->listsize = LIST_INIT_SIZE;
return 1;
}
//銷毀順序表
int DeleteList(SqList* L)
{
//1.判斷順序表是否存在
if (L->stu == NULL)//說明不存在
return 0;//不可以解引用NULL
//2.如果存在,則釋放對應的內存
free(L->stu);
L->stu = NULL;
//3.釋放內存后,恢復表的初始值
L->length = 0;
L->listsize = 0;
return 1;
}
//遍歷順序表
void FindAllList(SqList* L)
{
int i = 0;
for (i = 0;i < L->length;i++)
{
printf("age=%d,height=%d,weight=%lf\n", L->stu[i].age,
L->stu[i].height, L->stu[i].weight);
}
}
//查找學生數組中的某個元素,找到返回元素對應下標,找不到返回0
int FindOneList(SqList* L, Student* onestu3)
{
int i = 0;
while (i < L->length)
{
if ((L->stu[i].age == onestu3->age)
&& (L->stu[i].height == onestu3->height)
&& (L->stu[i].weight == onestu3->weight))
return i;
i++;
}
return -1;
}
//擴大數組長度
void ExpandList(SqList* L)
{
//1.申請內存
Student* p = (Student*)realloc(L->stu, (L->listsize + INCREASE) * sizeof(Student));
//2.判斷是否申請成功
if (!p)
exit(-1);
//3.如果申請到了內存,更新順序表的信息(包括學生數組、最大容納學生量)
L->stu = p;
L->listsize += INCREASE;
}
//元素復制
void CopyValue(Student* s1, Student* s2)
{
s1->age = s2->age;
s1->height = s2->height;
s1->weight = s2->weight;
}
//在順序表尾部插入元素
void InsertLastList(SqList* L, Student* onestu)
{
//1.判斷數組滿沒滿,滿就擴大數組長度
if (L->length >= L->listsize)
ExpandList(L);
//2.有足夠空間,在尾部插入新元素(將新元素拷貝到數組末尾)
CopyValue(&L->stu[L->length], onestu);
//3.更新學生數量
L->length++;
}
//在順序表頭部插入元素
void InsertFirstList(SqList* L, Student* onestu)
{
//1.判斷數組滿沒滿,滿就擴大數組長度
if (L->length >= L->listsize)
ExpandList(L);
//2.有足夠空間,先將所有元素向后挪動1位,
// 從后往前挪,要不然會被覆蓋
for (int i = L->length-1;i>=0;i--)
{
CopyValue(&L->stu[i + 1], &L->stu[i]);
}
//3.將新元素拷貝到數組開頭
CopyValue(&L->stu[0], onestu);
//4.更新學生數量
L->length++;
}
//在順序表指定位置插入元素
int InsertLocList(SqList* L, int i, Student* onestu)
{
//1.判斷位置是否合法
if (i < 0 || i >= L->length)
{
return 0;
}
//2.判斷數組是否有空位,沒有的話擴容
if (L->length == L->listsize)
{
ExpandList(L);
}
//3.將插入點及后面的元素向后移動1位
for (int j = L->length - 1;j >= i;j--)//j>=i+1
{
//注1:要從數組的最后一個元素依次向后挪動1位,如果從插入點
// 開始挪動的話,數組原先的內容會被覆蓋
//注2:j沒必要等于i,j--時值為i-1,會把插入點之前的值也往后移動1位
CopyValue(&L->stu[j + 1], &L->stu[j]);
}
//4.插入元素
CopyValue(&L->stu[i], onestu);
//5.更新表中的信息
L->length++;
return 1;
}
//提示輸入信息
void Print(Student* onestu)
{
printf("請輸入:\n");
printf("年齡:");
scanf("%d", &onestu->age);
printf("身高:");
scanf("%d", &onestu->height);
printf("體重:");
scanf("%lf", &onestu->weight);
}
//大規(guī)模插入數據
int InsertValue(SqList* L, int n)
{
//1.確保有足夠空間存放信息
while (L->listsize < n)
{
ExpandList(L);
if (L->listsize >= n)
break;
}
//2.有足夠空間,開始插入信息
for (int i = 0;i < n;i++)
{
Print(&L->stu[i]);
printf("已成功增加一組信息\n");
L->length++;
}
return 1;
}
//刪除一個元素(一組學生信息)
void DropOneValue(SqList*L,Student* onestu4)
{
//1.判斷是否有該組數據
int ret = FindOneList(L, onestu4);
if (ret == -1)
{
printf("沒有該信息\n");
return;
}
//2.有信息的話進行刪除
for (int i = ret + 1;i <= L->length - 1;i++)
{
CopyValue(&L->stu[i - 1], &L->stu[i]);
}
printf("刪除成功\n");
//3.成員數量信息變動
L->length--;
}
//更改一個元素(一組學生信息)
void ModifyOneValue(SqList* L, Student* onestu5, Student* onestu6)
{
//1.判斷該信息是否存在
int ret=FindOneList(L, onestu5);
if (ret == -1)
{
printf("沒有該信息\n");
return;
}
//2.信息存在,進行修改
printf("請輸入修改后信息:\n");
Print(onestu6);
CopyValue(&L->stu[ret], onestu6);
}
??三.主函數
int main()
{
//1.創(chuàng)建變量
SqList L;
Student onestu, onestu2,onestu3,
onestu4,onestu5,onestu6,onestu7;
//2.初始化(初步申請空間)
InitList(&L);
//3.初步整體性插入學生信息
printf("1.整體插入信息\n");
int n = 0;
printf("請輸入學生個數:\n");
scanf("%d", &n);
InsertValue(&L, n);
//4.在末尾處插入學生信息
printf("2.在數組末尾處插入學生信息\n");
Print(&onestu);
InsertLastList(&L, &onestu);
//5.在開頭處插入學生信息
printf("3.在數組開頭處插入學生信息\n");
Print(&onestu7);
InsertFirstList(&L, &onestu7);
//6.在指定位置插入學生信息
printf("4.在指定位置處插入學生信息\n");
printf("請輸入要插入的位置:");
int i = 0;
scanf("%d", &i);
Print(&onestu2);
InsertLocList(&L, i, &onestu2);
//7.查找學生數組中的某個元素
printf("5.查找某名學生\n");
Print(&onestu3);
int ret = FindOneList(&L, &onestu3);
if (ret == 0)
printf("沒有該名學生\n");
else
printf("該名學生的編號是%d\n", ret);
//8.刪除表中元素
printf("6.刪除表中一組信息:\n");
printf("請輸入要刪除的學生信息:\n");
Print(&onestu4);
DropOneValue(&L, &onestu4);
//9.修改信息
printf("7.修改表中信息\n");
printf("請輸入被修改學生信息:\n");
Print(&onestu5);
ModifyOneValue(&L, &onestu5, &onestu6);
//10.展示最終順序表(所有插入的信息)
printf("8.展示最終學生信息表\n");
FindAllList(&L);
//10.釋放空間
DeleteList(&L);
}
??運行結果
我在輸入學生信息的時候用數字代替了??文章來源:http://www.zghlxwxcb.cn/news/detail-620551.html
感謝瀏覽,如有錯誤請及時指正!??文章來源地址http://www.zghlxwxcb.cn/news/detail-620551.html
到了這里,關于數據結構之動態(tài)順序表(附帶完整程序)的文章就介紹完了。如果您還想了解更多內容,請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章,希望大家以后多多支持TOY模板網!