C語言超詳細講解順序表的各種操作
順序表是什么
順序表是在計算機內存中以數組的形式保存的線性表,線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素、使得線性表中在邏輯結構上相鄰的數據元素存儲在相鄰的物理存儲單元中,即通過數據元素物理存儲的相鄰關系來反映數據元素之間邏輯上的相鄰關系,采用順序存儲結構的線性表通常稱為順序表。順序表是將表中的結點依次存放在計算機內存中一組地址連續(xù)的存儲單元中。
?
總的來說,順序表類似于數組,下標對應的是相應的元素(如圖所示)
順序表的結構體
typedef struct { SLDataType *a; int size;//表示數組中存儲了多少個數據 int capacity;//數組實際存儲數據的空間容量是多大 }SL;
其中的SLDataType*a的意思是可以動態(tài)開辟空間--相當于數組,因為數組表示的是首元素的地址,這里是直接換成了指針,也指的是地址和數組的意思一樣!
typedef int SLDataType;//重命名,到時候方便更改類型
順序表的接口函數
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);//刪除中間某一個元素
這里只是先對一些函數進行聲名,還沒有進行創(chuàng)建函數!
順序表相關操作的菜單
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; SLDataType*tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));//SLDataType類型(強制類型轉換)的有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是擴容函數,是在ps->a后面擴容一個SLDataType類型(強制類型轉換)的有newcapacity大小的空間,申請成功的話,就讓指針a的地址存放新的地址tmp,此時新的地址tmp里面有擴容后的空間,再讓capacity為新的容量,讓ps的第一個位置放傳進來函數的x,最后再讓它的大小++。
陳列元素
void SepListdisplay(SL*ps)//陳列 { cout << "下面是您賦值的元素" << endl; for (int i = 0; i < ps->size; i++) { cout << ps->a[i] << " "; } cout << endl; }
陳列元素這塊很簡單,直接可以通過它的下標找到它所代表的值,跟數組一樣
往最后加元素
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函數進行重新分配空間,再直接讓最后一個位置里面放上傳過來的元素就可以了。
往前面加元素
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函數重新分配空間,此時要是想要在最前面添加元素的話,就需要先讓它的大小++,再讓從下標為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; }
要是想在任意位置加元素的話,我們首先應該知道我們需要進行加元素的下標,以及我們需要添加的元素,此時剛好我們的函數里面已經接收到了這兩個元素,此時我們就從這個下標開始,讓下標對應的元素以及下標之后的元素都往后加一個位置,此時就可以為新的元素騰出一個位置,等全部移動完成后,我們就可以把元素加進來就可以了。
刪除最后元素
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; }
我們這里可以直接讓從下標為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; }
這里的話我們已經知道我們需要刪除元素的下標了,于是我們就可以從這個下標開始不包括這個下標對應的元素 ,把它們的位置往前推一個,把該元素覆蓋住就可以了,最后再讓大小減一。
整體代碼(fun.h部分)
#pragma once #define N 10000 typedef int SLDataType; typedef struct { SLDataType *a; int size; int capacity; }SL; //接口函數 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>//順序表的實現 #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是擴容函數,是在ps->a后面擴容一個 //SLDataType類型(強制類型轉換)的有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是擴容函數,是在ps->a后面擴容一個 //SLDataType類型(強制類型轉換)的有newcapacity大小的空間 if (tmp == NULL)//如果分配失敗 { cout << "分配失敗" << endl; exit(-1); } ps->a = tmp;//申請成功的話,就讓指針a的地址存放新的地址tmp,此時新的地址tmp里面有擴容后的空間 ps->capacity = newcapacity;//再讓capacity為新的容量 } ps->a[ps->size] = x;//讓ps的第一個位置放傳進來函數的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是擴容函數,是在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; }
整體代碼(主函數部分)
#include<iostream>//順序表的實現 #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 << "請輸入您要添加位置的下標以及添加的元素" << endl; cin >> n >> m; SeqListPushMid(&ps, 1, 6); break; case 7: SeqListPopBack(&ps); break; case 8: SeqListPopFront(&ps); break; case 9: cout << "請輸入您要進行刪除元素的下標" << endl; cin >> n; SeqListPopMid(&ps, n); default: cout << "您的輸入有誤,請重新輸入" << endl; } } return 0; }
結果展示
到此這篇關于C語言超詳細講解順序表的各種操作的文章就介紹到這了,更多相關C語言順序表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
如何統(tǒng)計在一篇文章中某個單詞出現了幾次,以及第一次出現的位置
本文的主要內容就是統(tǒng)計某個單詞在一篇文章中出現了幾次,以及第一次出現的位置,需要的朋友可以參考下2015-08-08