各位CSDN的uu們你們好呀，今天小雅蘭又來更新新專欄啦，其實之前我就已經(jīng)寫過了順序表的內(nèi)容，只是之前的內(nèi)容不是最新版的順序表，現(xiàn)在，我來更新一下最新版的順序表，下面，就讓我們進入更新版的順序表的世界吧
順序表和小雅蘭之前寫的三子棋、掃雷、通訊錄一樣，分為三個文件：
https://xiaoyalan.blog.csdn.net/article/details/128705747?spm=1001.2014.3001.5502
https://xiaoyalan.blog.csdn.net/article/details/128717749?spm=1001.2014.3001.5502
https://xiaoyalan.blog.csdn.net/article/details/128717749?spm=1001.2014.3001.5502
https://xiaoyalan.blog.csdn.net/article/details/129788167?spm=1001.2014.3001.5502
https://xiaoyalan.blog.csdn.net/article/details/129896970?spm=1001.2014.3001.5502
test.c——測試代碼功能
SeqList.c——順序表的實現(xiàn)
SeqList.h——順序表的聲明
?https://xiaoyalan.blog.csdn.net/article/details/129380414?spm=1001.2014.3001.5502
這是小雅蘭之前寫的順序表的知識，有興趣的可以去看看
我們寫的是一個動態(tài)版的順序表：?
typedef struct SeqList { SLDataType* a; int size;//存儲的有效數(shù)據(jù)的個數(shù) int capacity;//容量 }SL;把struct SeqList這個結構體重命名為SL
typedef int SLDataType;?把int重命名為SLDataType
寫成這樣的形式是因為：如果以后想要修改類型，那就直接改int就可以了，如果不這樣寫，???????要改很多個地方，就很麻煩
順序表的初始化：
//初始化 void SLInit(SL* ps1) { ps1->a = malloc(sizeof(SLDataType) * 4); if (ps1 == NULL) { perror("malloc fail"); return; } ps1->size = 0; ps1->capacity = 4; }動態(tài)開辟出4個SLDataType類型的大小的空間
?順序表的銷毀：也就是把空間還給操作系統(tǒng)
//銷毀 //把空間還給操作系統(tǒng) void SLDestroy(SL* ps1) { free(ps1->a); ps1->a = NULL; ps1->size = 0; ps1->capacity = 0; }
打印順序表的內(nèi)容：
//打印 void SLPrint(SL* ps1) { int i = 0; for (i = 0; i < ps1->size; i++) { printf("%d ", ps1->a[i]); } printf("\n"); }
尾插：
ps1->a[ps1->size] = x; ps1->size++;在這里，我們需要想一個問題：在尾插的過程中，如果空間不夠了該怎么辦呢？？？所以在這里，我們還需要一個檢查容量的函數(shù)，如果容量不夠就擴容
//檢查容量，容量不夠就擴容 void SLCheckCapacity(SL* ps1) { if (ps1->size == ps1->capacity) { SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * ps1->capacity * 2); //擴上一個二倍大小的容量 //這個數(shù)值可以自己設定，擴多了不好，擴少了也不好 //所以擴上二倍是最合理的選擇 if (tmp == NULL) { perror("realloc fail"); return; } ps1->a = tmp; ps1->capacity = ps1->capacity * 2; } }//尾插 void SLPushBack(SL* ps1, SLDataType x) { SLCheckCapacity(ps1); ps1->a[ps1->size] = x; ps1->size++; }
下面，我們來測試一下尾插的功能，看是否成功
int main()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);
SLPushBack(&s, 6);
SLPushBack(&s, 7);
SLPushBack(&s, 8);
SLPushBack(&s, 9);
SLPushBack(&s, 10);
SLPrint(&s);
SLDestroy(&s);
return 0;
}
?結果發(fā)現(xiàn)，尾插的功能非常成功！??！
頭插：
需要從后往前挪動數(shù)據(jù)?。?！
?若是從前往后挪動數(shù)據(jù)，就會覆蓋，這是絕對不行的
//頭插 void SLPushFront(SL* ps1, SLDataType x) { SLCheckCapacity(ps1); //挪動數(shù)據(jù) int end = ps1->size - 1; while (end >= 0) { ps1->a[end + 1] = ps1->a[end];//把數(shù)據(jù)往后挪 end--; } ps1->a[0] = x; ps1->size++; }
來測試一下頭插的功能：
//頭插測試
void TestSeqList2()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushFront(&s, 5);
SLPushFront(&s, 6);
SLPushFront(&s, 7);
SLPushFront(&s, 8);
SLPushFront(&s, 9);
SLPrint(&s);
SLDestroy(&s);
}?
?尾刪：
?直接把size--就可以了
//尾刪 void SLPopBack(SL* ps1) { ps1->size--; }
?來測試一下尾刪的功能：
//尾刪測試
void TestSeqList3()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushFront(&s, 5);
SLPushFront(&s, 6);
SLPushFront(&s, 7);
SLPushFront(&s, 8);
SLPushFront(&s, 9);
SLPrint(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPrint(&s);
SLDestroy(&s);
}
但是這個尾刪仍然有點問題，需要檢查一下：
//尾刪 void SLPopBack(SL* ps1) { //溫柔的檢查 if (ps1->size == 0) { return; } ps1->size--; }//尾刪 void SLPopBack(SL* ps1) { //暴力的檢查 assert(ps1->size > 0); ps1->size--; }
?頭刪：
//頭刪 void SLPopFront(SL* ps1) { //暴力檢查 assert(ps1->size > 0); int start = 0; while (start < ps1->size - 1) { ps1->a[start] = ps1->a[start + 1]; start++; } ps1->size--; }
來測試一下頭刪的功能：
//頭刪測試
void TestSeqList4()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushFront(&s, 5);
SLPushFront(&s, 6);
SLPushFront(&s, 7);
SLPushFront(&s, 8);
SLPushFront(&s, 9);
SLPrint(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPrint(&s);
SLPopFront(&s);
SLPopFront(&s);
SLPopFront(&s);
SLPrint(&s);
SLDestroy(&s);
}?
在中間位置插入數(shù)據(jù)：
//在中間位置(pos)插入數(shù)據(jù) void SLInsert(SL* ps1, int pos, SLDataType x) { SLCheckCapacity(ps1); int end = ps1->size - 1; while (end >= pos) { ps1->a[end + 1] = ps1->a[end]; end--; } ps1->a[pos] = x; ps1->size++; }
寫了這個函數(shù)的功能之后，我們就可以把之前寫的頭插和尾插修改一下：
//尾插 void SLPushBack(SL* ps1, SLDataType x) { SLInsert(ps1, ps1->size, x); }//頭插 void SLPushFront(SL* ps1, SLDataType x) { SLInsert(ps1, 0, x); }
但是，這個在中間插入數(shù)據(jù)的代碼還是有點問題;
//中間插數(shù)據(jù)測試
void TestSeqList5()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushFront(&s, 5);
SLPushFront(&s, 6);
SLPushFront(&s, 7);
SLPushFront(&s, 8);
SLPushFront(&s, 9);
SLPrint(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPrint(&s);
SLPopFront(&s);
SLPopFront(&s);
SLPopFront(&s);
SLPrint(&s);
SLInsert(&s, 2, 30);
SLPrint(&s);
SLInsert(&s, 20, 300);
SLPrint(&s);
SLDestroy(&s);
}
從此運行結果可知：越界是不會報錯的?。?！但是它的的確確越界了?。?！
所以把代碼改進為：
//在中間位置(pos)插入數(shù)據(jù) void SLInsert(SL* ps1, int pos, SLDataType x) { assert(pos >= 0 && pos <= ps1->size); SLCheckCapacity(ps1); int end = ps1->size - 1; while (end >= pos) { ps1->a[end + 1] = ps1->a[end]; end--; } ps1->a[pos] = x; ps1->size++; }
在中間位置刪除數(shù)據(jù)：
//在中間位置(pos)刪除數(shù)據(jù) void SLErase(SL* ps1, int pos) { assert(pos >= 0 && pos < ps1->size); assert(ps1->size > 0);//可有可無 int start = pos + 1; while (start <= pos + 1) { ps1->a[start - 1] = ps1->a[start]; start++; } ps1->size--; }
同樣，有了這個功能之后，可以把頭刪和尾刪修改一下：
//頭刪 void SLPopFront(SL* ps1) { SLErase(ps1, 0); }//尾刪 void SLPopBack(SL* ps1) { SLErase(ps1, ps1->size - 1); }
測試一下從中間刪除數(shù)據(jù)的功能：
//中間刪數(shù)據(jù)測試
void TestSeqList6()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushFront(&s, 5);
SLPushFront(&s, 6);
SLPushFront(&s, 7);
SLPushFront(&s, 8);
SLPushFront(&s, 9);
SLPrint(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPrint(&s);
SLPopFront(&s);
SLPopFront(&s);
SLPopFront(&s);
SLPrint(&s);
SLInsert(&s, 2, 30);
SLPrint(&s);
SLErase(&s, 3);
SLPrint(&s);
SLDestroy(&s);
}?
?查找：
//查找 //找到了返回下標，找不到返回-1 int SLFind(SL* ps1, SLDataType x) { int i = 0; for (i = 0; i < ps1->size; i++) { if (ps1->a[i] == x) { return i; } } return -1; }
修改：
//修改 void SLModify(SL* ps1, int pos, SLDataType x) { assert(pos >= 0 && pos < ps1->size); ps1->a[pos] = x; }
下面，淺淺附上一波源代碼：
SeqList.c的內(nèi)容
#include"SeqList.h"
//初始化
void SLInit(SL* ps1)
{
assert(ps1);
ps1->a = malloc(sizeof(SLDataType) * 4);
if (ps1 == NULL)
{
perror("malloc fail");
return;
}
ps1->size = 0;
ps1->capacity = 4;
}
//銷毀
//把空間還給操作系統(tǒng)
void SLDestroy(SL* ps1)
{
assert(ps1);
free(ps1->a);
ps1->a = NULL;
ps1->size = 0;
ps1->capacity = 0;
}
//打印
void SLPrint(SL* ps1)
{
assert(ps1);
int i = 0;
for (i = 0; i < ps1->size; i++)
{
printf("%d ", ps1->a[i]);
}
printf("\n");
}
//檢查容量，容量不夠就擴容
void SLCheckCapacity(SL* ps1)
{
assert(ps1);
if (ps1->size == ps1->capacity)
{
SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * ps1->capacity * 2);
//擴上一個二倍大小的容量
//這個數(shù)值可以自己設定，擴多了不好，擴少了也不好
//所以擴上二倍是最合理的選擇
if (tmp == NULL)
{
perror("realloc fail");
return;
}
ps1->a = tmp;
ps1->capacity = ps1->capacity * 2;
}
}
//在中間位置(pos)插入數(shù)據(jù)
void SLInsert(SL* ps1, int pos, SLDataType x)
{
assert(ps1);
assert(pos >= 0 && pos <= ps1->size);
SLCheckCapacity(ps1);
int end = ps1->size - 1;
while (end >= pos)
{
ps1->a[end + 1] = ps1->a[end];
end--;
}
ps1->a[pos] = x;
ps1->size++;
}
//在中間位置(pos)刪除數(shù)據(jù)
void SLErase(SL* ps1, int pos)
{
assert(ps1);
assert(pos >= 0 && pos < ps1->size);
assert(ps1->size > 0);//可有可無
int start = pos + 1;
while (start <= pos + 1)
{
ps1->a[start - 1] = ps1->a[start];
start++;
}
ps1->size--;
}
//尾插
void SLPushBack(SL* ps1, SLDataType x)
{
assert(ps1);
/*SLCheckCapacity(ps1);
ps1->a[ps1->size] = x;
ps1->size++;*/
SLInsert(ps1, ps1->size, x);
}
//頭插
void SLPushFront(SL* ps1, SLDataType x)
{
assert(ps1);
//SLCheckCapacity(ps1);
挪動數(shù)據(jù)
//int end = ps1->size - 1;
//while (end >= 0)
//{
// ps1->a[end + 1] = ps1->a[end];//把數(shù)據(jù)往后挪
// end--;
//}
//ps1->a[0] = x;
//ps1->size++;
SLInsert(ps1, 0, x);
}
//尾刪
void SLPopBack(SL* ps1)
{
assert(ps1);
溫柔的檢查
//if (ps1->size == 0)
//{
// return;
//}
//ps1->size--;
//暴力的檢查
/*assert(ps1->size > 0);
ps1->size--;*/
SLErase(ps1, ps1->size - 1);
}
//頭刪
void SLPopFront(SL* ps1)
{
assert(ps1);
//暴力檢查
assert(ps1->size > 0);
int start = 0;
while (start < ps1->size - 1)
{
ps1->a[start] = ps1->a[start + 1];
start++;
}
ps1->size--;
//SLErase(ps1, 0);
}
//查找
//找到了返回下標，找不到返回-1
int SLFind(SL* ps1, SLDataType x)
{
assert(ps1);
int i = 0;
for (i = 0; i < ps1->size; i++)
{
if (ps1->a[i] == x)
{
return i;
}
}
return -1;
}
//修改
void SLModify(SL* ps1, int pos, SLDataType x)
{
assert(ps1);
assert(pos >= 0 && pos < ps1->size);
ps1->a[pos] = x;
}
SeqList.h的內(nèi)容
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//動態(tài)順序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size;//存儲的有效數(shù)據(jù)的個數(shù)
int capacity;//容量
}SL;
//初始化
void SLInit(SL* ps1);
//銷毀
//把空間還給操作系統(tǒng)
void SLDestroy(SL* ps1);
//打印
void SLPrint(SL* ps1);
//尾插
void SLPushBack(SL* ps1,SLDataType x);
//尾刪
void SLPopBack(SL* ps1);
//頭插
void SLPushFront(SL* ps1, SLDataType x);
//頭刪
void SLPopFront(SL* ps1);
//在中間位置(pos)插入數(shù)據(jù)
void SLInsert(SL* ps1, int pos, SLDataType x);
//在中間位置(pos)刪除數(shù)據(jù)
void SLErase(SL* ps1, int pos);
//查找
//找到了返回下標，找不到返回-1
int SLFind(SL* ps1, SLDataType x);
//修改
void SLModify(SL* ps1, int pos, SLDataType x);
test.c的內(nèi)容
void menu()
{
printf("***********************************************************\n");
printf("1、尾插數(shù)據(jù) 2、尾刪數(shù)據(jù)\n");
printf("\n");
printf("3、頭插數(shù)據(jù) 4、頭刪數(shù)據(jù)\n");
printf("\n");
printf("5、在任意位置插入數(shù)據(jù)（位置3插入20）\n");
printf("\n");
printf("6、在任意位置刪除數(shù)據(jù) \n");
printf("\n");
printf("7、查找某個數(shù)據(jù)的位置，并刪除它 \n");
printf("\n");
printf("8、刪除順序表中有的 某個數(shù)據(jù) \n");
printf("\n");
printf("9、打印數(shù)據(jù) \n");
printf("\n");
printf("-1、退出 \n");
printf("\n");
printf("***********************************************************\n");
}
int main()
{
printf("************* 歡迎大家來到動態(tài)順序表的測試 **************\n");
int option = 0;
SL s;
SLInit(&s);
do
{
menu();
printf("請輸入你的操作：>");
scanf_s("%d", &option);
int sum = 0;
int x = 0;
int y = 0;
int z = 0;
int pos = 0;
int w = 0;
switch (option)
{
case 1:
printf("請依次輸入你要尾插的數(shù)據(jù)：，以-1結束\n");
scanf_s("%d", &sum);
while (sum != -1)
{
SLPushBack(&s, sum); // 1.尾插
scanf_s("%d", &sum);
}
break;
case 2:
SLPopBack(&s); // 2.尾刪
break;
case 3:
scanf_s("%d", &x);
SLPushFront(&s, x); // 3.頭插
break;
case 4:
SLPopFront(&s); // 4.頭刪
break;
case 5:
SLInsert(&s, 3, 20); // 5.在任意位置插入數(shù)據(jù)
break;
case 6:
SLErase(&s, 3); // 6.在任意位置刪除數(shù)據(jù)
break;
case 7:
printf("請輸入要刪除序列的中的某個數(shù)字\n");
scanf_s("%d", &z);
y = SLFind(&s, z); // 7.查找某個數(shù)字的位置，并且刪除它
printf("%d的位置在%d處： \n", z, y);
if (y != -1)
{
SLErase(&s, y);
}
break;
case 8:
printf("請輸入要刪除序列的中的數(shù)字\n"); //8.刪除順序表中 所有的 某個數(shù)據(jù)
scanf_s("%d", &w);
pos = SLFind(&s, w, 0);
while (pos != -1)
{
SLErase(&s, pos);
pos = SLFind(&s, w, pos);
}
break;
case 9:
SLPrint(&s);
break;
default:
if (option == -1)
{
exit(0); // 退出程序
}
else
{
printf("輸入錯誤，請重新輸入\n");
}
break;
}
} while (option != -1); // 退出程序
SLDestroy(&s);
return 0;
}好啦，小雅蘭今天的順序表的更新版的內(nèi)容就到這里啦，繼續(xù)加油刷題和學習算法噢！??！文章來源：http://www.zghlxwxcb.cn/news/detail-422783.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-422783.html
到了這里，關于順序表（更新版）——“數(shù)據(jù)結構與算法”的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
