網(wǎng)站首頁 編程語言 正文
順序表概念：
? ? ? ? 順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)。一般情況下用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。
代碼解析：
一.準(zhǔn)備工作
1.?首先對(duì)一些頭文件的引用和創(chuàng)建一個(gè)結(jié)構(gòu)體，結(jié)構(gòu)體包含一個(gè)數(shù)組，size表示該數(shù)組目前有多少個(gè)元素，capacity表示目前數(shù)組能存多少個(gè)元素。例如：
?
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>
typedef int DataType;
typedef struct SeqList
{
DataType* a;
int size;
int capacity;
}SL;
2.創(chuàng)建一個(gè)順序表
SL sl;
二、順序表的基本操作?
1.順序表的初始化函數(shù)
? ? ? ? ?注意這里的參數(shù)得是指針，形參是實(shí)參的一份臨時(shí)拷貝，所以得把地址傳給函數(shù)才能改變值。
void SeqListInit(SL* sl)
{
sl->a = NULL;
sl->size = 0;
sl->capacity = 0;
}
2.尾插函數(shù)（在尾部插入數(shù)據(jù)）
? ? ? ? 寫尾插函數(shù)之前我們得先判斷一下數(shù)組空間是否夠。例如下面的例子。
所以我們要先檢查空間是否滿了，滿了就擴(kuò)容
將這個(gè)判斷空間函數(shù)命名為? void CheckSpace(SL* sl) （這是動(dòng)態(tài)順序表區(qū)別于靜態(tài)順序表最主要的部分）?
void CheckSpace(SL* sl)
{
if (sl->size == sl->capacity)
{
//因?yàn)閏apacity一開始等于0，所以先給capacity一個(gè)值
int newcapacity = sl->capacity == 0 ? 4 : sl->capacity * 2;
DataType* tmp = (DataType*)realloc(sl->a, sizeof(DataType)*newcapacity);
if (tmp == NULL)
{
printf("開辟失敗\n");
exit(-1);
}
else
{
sl->capacity = newcapacity;
sl->a = tmp;
}
}
}
尾插函數(shù)：
void SeqListPushBack(SL* sl, DataType x)
{
CheckSpace(sl);
sl->a[sl->size] = x;
sl->size++;
}
3.頭插函數(shù)（在數(shù)組頭部插入數(shù)據(jù)）
? ? ? ? 
void SeqListPushFront(SL* sl, DataType x)
{
//因?yàn)椴迦氲臅r(shí)候都要檢查空間是不是滿了，滿了就擴(kuò)容
CheckSpace(sl);
for (int end = sl->size - 1; end >= 0; end--)
{
sl->a[end + 1] = sl->a[end];
}
sl->a[0] = x;
sl->size++;
}
?挪數(shù)據(jù)對(duì)應(yīng)著for循環(huán)的代碼，最后再給數(shù)組的第一個(gè)位置賦值。別忘了對(duì)size+1.
?4.尾刪函數(shù)
? ? ? ? 如果size等于0了就說明順序表中沒有數(shù)據(jù)了，所以
void SeqListPopBack(SL* sl)
{
assert(sl->size > 0);
sl->size--;
}
5.頭刪函數(shù)
? ? ? ? 從第二個(gè)數(shù)據(jù)開始整體往前挪以為就可以了。（要從前面開始挪）：
void SeqListPopFront(SL* sl)
{
for (int i = 1; i < sl->size; i++)
{
sl->a[i - 1] = sl->a[i];
}
sl->size--;
}
6.在第pos的位置插入數(shù)據(jù)
? ? ? ? 首先pos不能小于現(xiàn)有的數(shù)據(jù)個(gè)數(shù)。
? ? ? ? 第二判斷空間，滿了就擴(kuò)容。
? ? ? ? 第三：從第pos個(gè)位置的數(shù)據(jù)開始（這里第pos個(gè)位置的數(shù)據(jù)在數(shù)組中的下標(biāo)是pos-1）?將后面的數(shù)據(jù)整體往后挪一位。
? ? ? ? 第四：再這個(gè)位置賦值，別忘了對(duì)size++；
void SeqListInsert(SL* sl, int pos, DataType x)
{
//查看空間
assert(pos <= sl->size);
CheckSpace(sl);
for (int end = sl->size-1; end >= pos-1; end--)//這里不能用sl->size--
{
sl->a[end+1] = sl->a[end];
}
sl->a[pos - 1] = x;
sl->size++;
}
7.刪除第pos個(gè)位置的數(shù)據(jù)
? ? ? ? 首先pos不能小于現(xiàn)有數(shù)據(jù)個(gè)數(shù)
? ? ? ? 第二：將從第pos個(gè)位置的數(shù)據(jù)開始到最后一個(gè)數(shù)據(jù)往前挪一位
? ? ? ? 第三：對(duì)size--?
void SeqListErase(SL* sl, int pos)
{
assert(pos <=sl->size);
for (int i = pos; i < sl->size; i++)
{
sl->a[i - 1] = sl->a[i];
}
sl->size--;
}
8.修改第pos個(gè)位置的數(shù)據(jù)
? ? ? ? 一：pos不能小于現(xiàn)有數(shù)據(jù)個(gè)數(shù)
? ? ? ? 二：賦值。第pos個(gè)位置的數(shù)據(jù)在數(shù)組中下標(biāo)是pos-1。（因?yàn)閿?shù)組下表從0開始）
void SeqListModify(SL* sl, int pos, DataType x)
{
assert(pos <= sl->size);
sl->a[pos - 1] = x;
}
9.查找函數(shù)。
? ? ? ? 遍歷一遍看是否有這個(gè)數(shù)據(jù)，有就返回?cái)?shù)據(jù)是第幾個(gè)元素。（這里我不是返回該數(shù)據(jù)在數(shù)組中的下標(biāo)，我是返回 下標(biāo)+1）?
? ? ? ? 這里我沒有考慮如果有兩個(gè)一樣的數(shù)據(jù)的情況。
int SeqListFind(SL* sl, DataType x)
{
for (int i = 0; i < sl->size;i++)
{
if (sl->a[i] == x)
{
i++;
printf("在第%d個(gè)位置\n", i);
return i;
}
}
printf("沒有此數(shù)據(jù)\n");
return -1;
}
10.銷毀函數(shù)
? ? ? ? 釋放sl->a之后要對(duì)它置空，因?yàn)橹羔榝ree之后,free函數(shù)只是把指針指向的內(nèi)存空間釋放了,即內(nèi)存中存儲(chǔ)的值,但是并沒有將指針的值賦為NULL,指針仍然指向這塊內(nèi)存。?
void SeqListDestory(SL* sl)
{
free(sl->a);
sl->a = NULL;
sl->size = 0;
sl->capacity = 0;
}
11.打印函數(shù)
void SeqListPrint(SL* sl)
{
for (int i = 0; i < sl->size;i++)
{
printf("%d ", sl->a[i]);
}
printf("\n");
}
三、總代碼：
? ? ? ? 菜單寫的比較簡單。
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>
typedef int DataType;
typedef struct SeqList
{
DataType* a;
int size;
int capacity;
}SL;
void SeqListInit(SL* sl)
{
sl->a = NULL;
sl->size = 0;
sl->capacity = 0;
}
void SeqListPrint(SL* sl)
{
for (int i = 0; i < sl->size; i++)
{
printf("%d ", sl->a[i]);
}
printf("\n");
}
void CheckSpace(SL* sl)
{
if (sl->size == sl->capacity)
{
//因?yàn)閏apacity一開始等于0，所以先給capacity一個(gè)值
int newcapacity = sl->capacity == 0 ? 4 : sl->capacity * 2;
DataType* tmp = (DataType*)realloc(sl->a, sizeof(DataType)*newcapacity);
if (tmp == NULL)
{
printf("開辟失敗\n");
exit(-1);
}
else
{
sl->capacity = newcapacity;
sl->a = tmp;
}
}
}
void SeqListPushBack(SL* sl, DataType x)
{
//看空間是不是滿了，滿了就擴(kuò)容
//if (sl->size == sl->capacity)
//{
// //因?yàn)閏apacity一開始等于0，所以先給capacity一個(gè)值
// int newcapacity = sl->capacity == 0 ? 4 : sl->capacity * 2;
// DataType* tmp = (DataType*)realloc(sl->a, sizeof(DataType)*newcapacity);
// if (tmp == NULL)
// {
// printf("開辟失敗\n");
// exit(-1);
// }
// else
// {
// sl->a = tmp;
// }
//}
//封裝成一個(gè)函數(shù)
CheckSpace(sl);
sl->a[sl->size] = x;
sl->size++;
}
void SeqListPushFront(SL* sl, DataType x)
{
//因?yàn)椴迦氲臅r(shí)候都要檢查空間是不是滿了，滿了就擴(kuò)容
CheckSpace(sl);
for (int end = sl->size - 1; end >= 0; end--)
{
sl->a[end + 1] = sl->a[end];
}
sl->a[0] = x;
sl->size++;
}
void SeqListPopBack(SL* sl)
{
assert(sl->size > 0);
sl->size--;
}
void SeqListPopFront(SL* sl)
{
for (int i = 1; i < sl->size; i++)
{
sl->a[i - 1] = sl->a[i];
}
sl->size--;
}
void SeqListInsert(SL* sl, int pos, DataType x)
{
//查看空間
assert(pos <= sl->size);
CheckSpace(sl);
for (int end = sl->size - 1; end >= pos - 1; end--)//這里不能用sl->size--
{
sl->a[end + 1] = sl->a[end];
}
sl->a[pos - 1] = x;
sl->size++;
}
void SeqListErase(SL* sl, int pos)
{
assert(pos <= sl->size);
for (int i = pos; i < sl->size; i++)
{
sl->a[i - 1] = sl->a[i];
}
sl->size--;
}
void SeqListModify(SL* sl, int pos, DataType x)
{
assert(pos <= sl->size);
sl->a[pos - 1] = x;
}
int SeqListFind(SL* sl, DataType x)
{
for (int i = 0; i < sl->size; i++)
{
if (sl->a[i] == x)
{
i++;
printf("在第%d個(gè)位置\n", i);
return i;
}
}
printf("沒有此數(shù)據(jù)\n");
return -1;
}
void SeqListDestory(SL* sl)
{
free(sl->a);
sl->a = NULL;
sl->size = 0;
sl->capacity = 0;
}
void menu()
{
printf("******************************\n");
printf("*** 1.尾插數(shù)據(jù) 2.頭插數(shù)據(jù) ***\n");
printf("*** 3.在第pos個(gè)位置插入數(shù)據(jù)***\n");
printf("*** 4.尾刪數(shù)據(jù) 5.頭刪數(shù)據(jù) ***\n");
printf("*** 6.在第pos個(gè)位置刪除數(shù)據(jù)***\n");
printf("*** 7.修改第pos個(gè)位置的數(shù)據(jù)***\n");
printf("*** 8.查找數(shù)據(jù) 9.打印數(shù)據(jù) ***\n");
printf("********** -1.退出 ***********\n");
printf("******************************\n");
}
int main()
{
SL sl;
SeqListInit(&sl);
int option = 0;
int x = 0;
int pos = 1;
while (option != -1)
{
menu();
scanf("%d", &option);
switch (option)
{
case 1:
printf("請(qǐng)輸入要插入的數(shù)據(jù)，以-1結(jié)束：\n");
do
{
scanf("%d", &x);
if (x != -1)
{
SeqListPushBack(&sl, x);
}
} while (x != -1);
break;
case 2:
printf("請(qǐng)輸入要插入的數(shù)據(jù)，以-1結(jié)束：\n");
do
{
scanf("%d", &x);
if (x != -1)
{
SeqListPushFront(&sl, x);
}
} while (x != -1);
break;
case 3:
printf("請(qǐng)輸入要插入的數(shù)據(jù)，要從第幾個(gè)插入,以非正正數(shù)結(jié)束\n");
do
{
scanf("%d", &x);
scanf("%d", &pos);
if (pos >= 0)
{
SeqListInsert(&sl, pos, x);
}
} while (pos >= 0);
break;
case 4:
SeqListPopBack(&sl);
break;
case 5:
SeqListPopFront(&sl);
break;
case 6:
printf("請(qǐng)輸入要?jiǎng)h除第幾個(gè)位置的數(shù)據(jù)，以非正正數(shù)結(jié)束\n");
do
{
scanf("%d", &pos);
if (pos>0)
{
SeqListErase(&sl, pos);
}
} while (pos>0);
break;
case 7:
printf("請(qǐng)輸入要修改的數(shù)據(jù)，要修改第幾個(gè)數(shù)據(jù),以非正整數(shù)結(jié)束\n");
do
{
scanf("%d", &x);
scanf("%d", &pos);
if (pos>0)
{
SeqListInsert(&sl, pos, x);
}
} while (pos>0);
break;
case 8:
printf("請(qǐng)輸入需要查找的數(shù)據(jù)\n");
scanf("%d", &x);
SeqListFind(&sl, x);
break;
case 9:
SeqListPrint(&sl);
break;
case -1:
printf("退出\n");
break;
default:
printf("輸入錯(cuò)誤，請(qǐng)重新輸入\n");
}
}
SeqListDestory(&sl);
return 0;
}
原文鏈接：https://blog.csdn.net/weixin_53936115/article/details/122013467
相關(guān)推薦
- 2024-01-14 springboot-mybatis/JPA流式查詢
- 2022-05-13 C語言中的輸入與輸出
- 2023-04-24 一文帶你深入了解C++中音頻PCM數(shù)據(jù)_C 語言
- 2022-07-08 go語言代碼生成器code?generator使用示例介紹_Golang
- 2022-10-05 python中內(nèi)置庫os與sys模塊的詳細(xì)介紹_python
- 2022-06-28 go?micro集成鏈路跟蹤的方法和中間件原理解析_Golang
- 2022-08-31 C語言數(shù)據(jù)的存儲(chǔ)專項(xiàng)分析_C 語言
- 2023-01-20 pandas中df.groupby()方法深入講解_python
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動(dòng)態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對(duì)象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速