C語言超詳細講解順序表的各種操作
順序表是什么
順序表是在計算機內(nèi)存中以數(shù)組的形式保存的線性表,線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素、使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲在相鄰的物理存儲單元中,即通過數(shù)據(jù)元素物理存儲的相鄰關(guān)系來反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系,采用順序存儲結(jié)構(gòu)的線性表通常稱為順序表。順序表是將表中的結(jié)點依次存放在計算機內(nèi)存中一組地址連續(xù)的存儲單元中。
?
總的來說,順序表類似于數(shù)組,下標(biāo)對應(yīng)的是相應(yīng)的元素(如圖所示)
順序表的結(jié)構(gòu)體
typedef struct { SLDataType *a; int size;//表示數(shù)組中存儲了多少個數(shù)據(jù) int capacity;//數(shù)組實際存儲數(shù)據(jù)的空間容量是多大 }SL;
其中的SLDataType*a的意思是可以動態(tài)開辟空間--相當(dāng)于數(shù)組,因為數(shù)組表示的是首元素的地址,這里是直接換成了指針,也指的是地址和數(shù)組的意思一樣!
typedef int SLDataType;//重命名,到時候方便更改類型
順序表的接口函數(shù)
void menu();//菜單
void SeqListInit(SL*ps);//初始化
void SeqListPushBack(SL*ps, SLDataType x);//往后加元素
void SeqListPush(SL*ps, SLDataType n);//在順序表中添加元素
void SeqListPopBack(SL*ps);//刪除最后一個元素
void SeqListPushFront(SL*ps, SLDataType x);//往前面加元素
void SeqListPopFront(SL*ps);//刪除第一個元素
void SepListdisplay(SL*ps);//陳列
void SeqListPushMid(SL*ps, SLDataType x,SLDataType z);//往中間加元素
void SeqListPopMid(SL*ps,SLDataType x);//刪除中間某一個元素
這里只是先對一些函數(shù)進行聲名,還沒有進行創(chuàng)建函數(shù)!
順序表相關(guān)操作的菜單
void menu() { cout << "\t\t\t******************************************************************" << endl; cout << "\t\t\t**************** 注意!每次都要先進行初始化 *******************" << endl; cout << "\t\t\t**************** 1.輸入-1 退出程序 *******************" << endl; cout << "\t\t\t**************** 2.輸入1 初始化 *******************" << endl; cout << "\t\t\t**************** 3.輸入2 添加元素 *******************" << endl; cout << "\t\t\t**************** 4.輸入3 陳列元素 *******************" << endl; cout << "\t\t\t**************** 5.輸入4 往最后加元素 *******************" << endl; cout << "\t\t\t**************** 6.輸入5 往前面加元素 *******************" << endl; cout << "\t\t\t**************** 7.輸入6 任意位置加元素 *******************" << endl; cout << "\t\t\t**************** 8.輸入7 刪除最后元素 *******************" << endl; cout << "\t\t\t**************** 8.輸入8 刪除前面元素 *******************" << endl; cout << "\t\t\t**************** 8.輸入9 刪除任意元素 *******************" << endl; cout << "\t\t\t******************************************************************" << endl; }
可以在控制臺輸入相關(guān)的數(shù)字進行相關(guān)的操作
順序表的初始化
void SeqListInit(SL*ps)//初始化 { ps->a = NULL; ps->size = ps->capacity = 0; cout << "初始化完成" << endl; }
順序表初始化,首先使順序表的指針置為空,先讓順序表的長度和容量都先置為空
添加元素
void SeqListPush(SL*ps, SLDataType n) { if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 100 : ps->capacity * 2; SLDataType*tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));//SLDataType類型(強制類型轉(zhuǎn)換)的有newcapacity大小的空間 if (tmp == NULL) { cout << "分配失敗" << endl; exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } int k = 0; cout << "請進行賦值" << endl; for (int i = 0; i < n; i++) { cin >> k; ps->a[i] = k; ps->size++; } cout << "賦值完成" << endl; }
此時先進行判斷,如果沒有空間或者空間不足,就要把把一個新的容量賦值為原來容量的二倍,如果是0就賦值為100 。relloc是擴容函數(shù),是在ps->a后面擴容一個SLDataType類型(強制類型轉(zhuǎn)換)的有newcapacity大小的空間,申請成功的話,就讓指針a的地址存放新的地址tmp,此時新的地址tmp里面有擴容后的空間,再讓capacity為新的容量,讓ps的第一個位置放傳進來函數(shù)的x,最后再讓它的大小++。
陳列元素
void SepListdisplay(SL*ps)//陳列 { cout << "下面是您賦值的元素" << endl; for (int i = 0; i < ps->size; i++) { cout << ps->a[i] << " "; } cout << endl; }
陳列元素這塊很簡單,直接可以通過它的下標(biāo)找到它所代表的值,跟數(shù)組一樣
往最后加元素
void SeqListPushBack(SL*ps, SLDataType x) { if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 100 : ps->capacity * 2; SLDataType*tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType)); if (tmp == NULL)//如果分配失敗 { cout << "分配失敗" << endl; exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->size] = x; ps->size++;//再讓它的大小++ cout << "添加完成" << endl; }
此時還是要先進行判斷順序表的空間夠不夠,要是空間不夠的話,再運用realloc函數(shù)進行重新分配空間,再直接讓最后一個位置里面放上傳過來的元素就可以了。
往前面加元素
void SeqListPushFront(SL*ps, SLDataType x) { if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 100 : ps->capacity * 2; SLDataType*tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType)); if (tmp == NULL) { cout << "分配失敗" << endl; exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->size++; int i = 0; int j = ps->size; for (i = j; i > 0; i--) { ps->a[i] = ps->a[i - 1]; } ps->a[0] = x; cout << "添加完成" << endl; }
往前面加元素的話,首先還是需要進行判斷空間夠不夠,要是不夠還是要運用realloc函數(shù)重新分配空間,此時要是想要在最前面添加元素的話,就需要先讓它的大小++,再讓從下標(biāo)為0的第一個元素開始,把每一個元素都往后移動一個位置。移動完成之后,再讓新的元素加入的順序表的表頭就可以了。
任意位置加元素
void SeqListPushMid(SL*ps, SLDataType x,SLDataType z) { ps->size++; int i = 0; int j = ps->size - 1; for (i=j; i >= x; i--) { ps->a[i + 1] = ps->a[i]; } ps->a[x] = z; cout << "添加完成" << endl; }
要是想在任意位置加元素的話,我們首先應(yīng)該知道我們需要進行加元素的下標(biāo),以及我們需要添加的元素,此時剛好我們的函數(shù)里面已經(jīng)接收到了這兩個元素,此時我們就從這個下標(biāo)開始,讓下標(biāo)對應(yīng)的元素以及下標(biāo)之后的元素都往后加一個位置,此時就可以為新的元素騰出一個位置,等全部移動完成后,我們就可以把元素加進來就可以了。
刪除最后元素
void SeqListPopBack(SL*ps)//刪除最后一個元素 { if (ps->size > 0) { ps->size--; } cout << "刪除完畢" << endl; }
這一塊是最簡單的了,直接讓順序表的大小--就可以了。
刪除前面元素
void SeqListPopFront(SL*ps)//刪除第一個元素 { int i = 0; int j = ps->size; for (i = 1; i < j ; i++) { ps->a[i-1] = ps->a[i]; } ps->size--; cout << "刪除完畢" << endl; }
我們這里可以直接讓從下標(biāo)為1以及后面的元素的位置往前面加一個位置,把第一個元素覆蓋住就可以了。
刪除任意元素
void SeqListPopMid(SL*ps, SLDataType x)//刪除中間某一元素 { int i = 0, j = 0; for (i = x; i < ps->size ; i++) { ps->a[i] = ps->a[i + 1]; } ps->size--; cout << "刪除完畢" << endl; }
這里的話我們已經(jīng)知道我們需要刪除元素的下標(biāo)了,于是我們就可以從這個下標(biāo)開始不包括這個下標(biāo)對應(yīng)的元素 ,把它們的位置往前推一個,把該元素覆蓋住就可以了,最后再讓大小減一。
整體代碼(fun.h部分)
#pragma once #define N 10000 typedef int SLDataType; typedef struct { SLDataType *a; int size; int capacity; }SL; //接口函數(shù) void menu();//菜單 void SeqListInit(SL*ps);//初始化 void SeqListPushBack(SL*ps, SLDataType x);//往后加元素 void SeqListPush(SL*ps, SLDataType n);//在順序表中添加元素 void SeqListPopBack(SL*ps);//刪除最后一個元素 void SeqListPushFront(SL*ps, SLDataType x);//往前面加元素 void SeqListPopFront(SL*ps);//刪除第一個元素 void SepListdisplay(SL*ps);//陳列 void SeqListPushMid(SL*ps, SLDataType x,SLDataType z);//往中間加元素 void SeqListPopMid(SL*ps,SLDataType x);//刪除中間某一個元素
整體代碼(fun.cpp部分)
#include<iostream>//順序表的實現(xiàn) #include<stdlib.h> #include"fun.h" using namespace std; void menu() { cout << "\t\t\t******************************************************************" << endl; cout << "\t\t\t**************** 注意!每次都要先進行初始化 *******************" << endl; cout << "\t\t\t**************** 1.輸入-1 退出程序 *******************" << endl; cout << "\t\t\t**************** 2.輸入1 初始化 *******************" << endl; cout << "\t\t\t**************** 3.輸入2 添加元素 *******************" << endl; cout << "\t\t\t**************** 4.輸入3 陳列元素 *******************" << endl; cout << "\t\t\t**************** 5.輸入4 往最后加元素 *******************" << endl; cout << "\t\t\t**************** 6.輸入5 往前面加元素 *******************" << endl; cout << "\t\t\t**************** 7.輸入6 任意位置加元素 *******************" << endl; cout << "\t\t\t**************** 8.輸入7 刪除最后元素 *******************" << endl; cout << "\t\t\t**************** 8.輸入8 刪除前面元素 *******************" << endl; cout << "\t\t\t**************** 8.輸入9 刪除任意元素 *******************" << endl; cout << "\t\t\t******************************************************************" << endl; } void SeqListInit(SL*ps)//初始化 { ps->a = NULL; ps->size = ps->capacity = 0; cout << "初始化完成" << endl; } void SeqListPush(SL*ps, SLDataType n)//在順序表中加元素 { if (ps->size == ps->capacity)//如果沒有空間或者空間不足 { int newcapacity = ps->capacity == 0 ? 100 : ps->capacity * 2;//把一個新的容量賦值為原來容量的二倍,如果是0就賦值為100 SLDataType*tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));//relloc是擴容函數(shù),是在ps->a后面擴容一個 //SLDataType類型(強制類型轉(zhuǎn)換)的有newcapacity大小的空間 if (tmp == NULL)//如果分配失敗 { cout << "分配失敗" << endl; exit(-1); } ps->a = tmp;//申請成功的話,就讓指針a的地址存放新的地址tmp,此時新的地址tmp里面有擴容后的空間 ps->capacity = newcapacity;//再讓capacity為新的容量 } int k = 0; cout << "請進行賦值" << endl; for (int i = 0; i < n; i++) { cin >> k; ps->a[i] = k; ps->size++; } cout << "賦值完成" << endl; } void SeqListPushBack(SL*ps, SLDataType x)//往后加元素,或者也可以叫做為順序表賦值 { if (ps->size == ps->capacity)//如果沒有空間或者空間不足 { int newcapacity = ps->capacity == 0 ? 100 : ps->capacity * 2;//把一個新的容量賦值為原來容量的二倍,如果是0就賦值為100 SLDataType*tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));//relloc是擴容函數(shù),是在ps->a后面擴容一個 //SLDataType類型(強制類型轉(zhuǎn)換)的有newcapacity大小的空間 if (tmp == NULL)//如果分配失敗 { cout << "分配失敗" << endl; exit(-1); } ps->a = tmp;//申請成功的話,就讓指針a的地址存放新的地址tmp,此時新的地址tmp里面有擴容后的空間 ps->capacity = newcapacity;//再讓capacity為新的容量 } ps->a[ps->size] = x;//讓ps的第一個位置放傳進來函數(shù)的x ps->size++;//再讓它的大小++ cout << "添加完成" << endl; } void SeqListPopBack(SL*ps)//刪除最后一個元素 { if (ps->size > 0) { ps->size--; } cout << "刪除完畢" << endl; } void SeqListPushFront(SL*ps, SLDataType x)//往前面加元素 { //進來先判斷一下里面的空間滿沒有 if (ps->size == ps->capacity)//如果沒有空間或者空間不足 { int newcapacity = ps->capacity == 0 ? 100 : ps->capacity * 2;//把一個新的容量賦值為原來容量的二倍,如果是0就賦值為100 SLDataType*tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));//relloc是擴容函數(shù),是在ps->a后面擴容一個 //SLDataType類型的有newcapacity大小的空間 if (tmp == NULL)//如果分配失敗 { cout << "分配失敗" << endl; exit(-1); } ps->a = tmp;//申請成功的話,就讓指針a的地址存放新的地址tmp,此時新的地址tmp里面有擴容后的空間 ps->capacity = newcapacity;//再讓capacity為新的容量 } ps->size++; int i = 0; int j = ps->size; for (i = j; i > 0; i--) { ps->a[i] = ps->a[i - 1]; } ps->a[0] = x; cout << "添加完成" << endl; } void SeqListPopFront(SL*ps)//刪除第一個元素 { int i = 0; int j = ps->size; for (i = 1; i < j ; i++) { ps->a[i-1] = ps->a[i]; } ps->size--; cout << "刪除完畢" << endl; } void SepListdisplay(SL*ps)//陳列 { cout << "下面是您賦值的元素" << endl; for (int i = 0; i < ps->size; i++) { cout << ps->a[i] << " "; } cout << endl; } void SeqListPushMid(SL*ps, SLDataType x,SLDataType z)//往中間加元素 { ps->size++; int i = 0; int j = ps->size - 1; for (i=j; i >= x; i--) { ps->a[i + 1] = ps->a[i]; } ps->a[x] = z; cout << "添加完成" << endl; } void SeqListPopMid(SL*ps, SLDataType x)//刪除中間某一元素 { int i = 0, j = 0; for (i = x; i < ps->size ; i++) { ps->a[i] = ps->a[i + 1]; } ps->size--; cout << "刪除完畢" << endl; }
整體代碼(主函數(shù)部分)
#include<iostream>//順序表的實現(xiàn) #include<stdlib.h> #include"fun.h" using namespace std; int main() { SL ps; int n = 0, m = 0; int x = 0; menu(); while (cin >> x) { if (x < 0) { break; } switch (x) { case 1: SeqListInit(&ps); break; case 2: cout << "請輸入您要添加幾個元素" << endl; cin >> n; SeqListPush(&ps, n); break; case 3: SepListdisplay(&ps); break; case 4: cout << "請輸入您要在最后添加什么元素" << endl; cin >> n; SeqListPushBack(&ps, n); break; case 5: cout << "請輸入您要在最前面添加什么元素" << endl; cin >> n; SeqListPushFront(&ps, n); break; case 6: cout << "請輸入您要添加位置的下標(biāo)以及添加的元素" << endl; cin >> n >> m; SeqListPushMid(&ps, 1, 6); break; case 7: SeqListPopBack(&ps); break; case 8: SeqListPopFront(&ps); break; case 9: cout << "請輸入您要進行刪除元素的下標(biāo)" << endl; cin >> n; SeqListPopMid(&ps, n); default: cout << "您的輸入有誤,請重新輸入" << endl; } } return 0; }
結(jié)果展示
到此這篇關(guān)于C語言超詳細講解順序表的各種操作的文章就介紹到這了,更多相關(guān)C語言順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++實現(xiàn)inline hook的原理及應(yīng)用實例
這篇文章主要介紹了C++實現(xiàn)inline hook的原理及應(yīng)用,需要的朋友可以參考下2014-08-08C語言數(shù)據(jù)結(jié)構(gòu)中串的模式匹配
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)中串的模式匹配的相關(guān)資料,需要的朋友可以參考下2017-05-05C++實現(xiàn)LeetCode(94.二叉樹的中序遍歷)
這篇文章主要介紹了C++實現(xiàn)LeetCode(94.二叉樹的中序遍歷),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07如何統(tǒng)計在一篇文章中某個單詞出現(xiàn)了幾次,以及第一次出現(xiàn)的位置
本文的主要內(nèi)容就是統(tǒng)計某個單詞在一篇文章中出現(xiàn)了幾次,以及第一次出現(xiàn)的位置,需要的朋友可以參考下2015-08-08Qt實現(xiàn)UDP多線程數(shù)據(jù)處理及發(fā)送的簡單實例
本文主要介紹了Qt實現(xiàn)UDP多線程數(shù)據(jù)處理及發(fā)送的簡單實例,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2021-10-10c語言函數(shù)棧幀的創(chuàng)建和銷毀過程詳解
我們知道c語言中函數(shù)都是被調(diào)用的,main函數(shù)里面能調(diào)用其他函數(shù),其實main函數(shù)也是被別的函數(shù)調(diào)用的,下面通過本文給大家分享c語言函數(shù)棧幀的創(chuàng)建和銷毀過程,一起看看吧2021-08-08詳解C++中stoi/stol/stoll函數(shù)的用法
這篇文章主要為大家詳細介紹了C++中stoi、stol、stoll函數(shù)的具體用法,文中的示例代碼講解詳細,對我們學(xué)校C++有一點的幫助,需要的可以參考一下2023-03-03