線性表與順序表
💨順序表和之前的通訊錄有些相似
💨通訊錄原始碼地址：通訊錄原始碼
💨通訊錄文章：通訊錄筆記
🐋順序表原始碼：順序表原始碼
🐋順序表筆記：順序表筆記
文章目錄
- 線性表與順序表
- 一、線性表
- 二、順序表
- 1. 靜態順序表
- 2. 動態順序表
- 2.1 定義一個動態的順序表
- 2.2 初始化順序表
- 2.3 順序表開辟記憶體
- 2.4 順序表尾插
- 2.5 列印順序表
- 2.6 順序表頭插
- 2.7 順序表尾刪
- 2.8 順序表頭刪
- 2.9 順序表查找
- 3.0 順序表中間插入
- 3.1 順序表中間洗掉
- 3.2 測驗
一、線性表
線性表(linear list)是n個具有相同特性的資料元素的有限序列，是一種很常見的資料結構線性表在
邏輯上是線性結構，但是在物理結構上并不一定是連續的
常見的線性表有：順序表、鏈表、堆疊、佇列、字串等
二、順序表
順序表(seqlist)是物理地址連續的存盤元素的線性結構，一般情況下采用陣列存盤,在陣列上完成資料的增刪查改可以認為，順序表的本質就是
陣列
1. 靜態順序表
靜態其實就是固定長度的陣列
之前在通訊錄中寫過
#define BOOK_MAX 100
typedef int DataType //這樣可以隨時改變內容的型別
typedef struct address_book //通訊錄內容
{
struct perinfmt p[BOOK_MAX];//每個人資訊,陣列一共100個人
DataType ID;//統計每個人編號
}SeqlistContact;//順序表
這樣一個內容就是一個靜態順序表
2. 動態順序表
當我們不滿足于100個人固定長度的通訊錄的時候
又或者是因為100個人的通訊錄太長時候
🐠🐠我們選擇記憶體可以動態開辟，這樣想改變大小的時候都很自由
//動態通訊錄
struct address_book
{
struct perinfmt* p;//這里就是位動態記憶體陣列所準備的起始地址
int ID;
int allID;
};
以它為例，我們來寫一個比較通用的順序表，型別不再是固定的了，并且把順序表的增刪查改都寫出來
2.1 定義一個動態的順序表
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a;
size_t size;
size_t capacity;
}SL;
2.2 初始化順序表
void SeqListInit(SL* ps)//初始化順序表
{
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
這一步也很簡單，把指標設定為空，其他賦值0即可
2.3 順序表開辟記憶體
在順序表尾插函式之前，我們先按照這個邏輯來，初始化好往里面賦值
這就考慮到順序表記憶體滿了沒有，滿了需要開辟再存
兩種情況需要開辟記憶體
- 🐬剛開始空間記憶體還未開辟
- 🐬空間滿了，默認擴大為原來的二倍
以后的插入判斷記憶體滿了沒有，所以我們單獨寫一個函式判斷并開辟空間
//查看順序表空間是否滿了
void SeqListCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = (ps->capacity == 0) ? 2 : (ps->capacity * 2);//如果沒有開辟開辟2，開辟了滿了開辟2倍
SL* tmp = (SL*)reallco(ps->a, sizeof(SL) * newcapacity);
if (tmp == NULL)
{
exit(-1);//開辟失敗
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
2.4 順序表尾插
先判斷有沒有滿，再插入
//順序表尾插
void SeqListPushBack(SL* ps, SLDateType x)
{
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
2.5 列印順序表
輸入完資料后，列印該資料看看效果
//列印順序表
void SeqListPrint(SL* ps)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
2.6 順序表頭插
需要倒著把數字都挪到最右邊
不過在這之前也需要判斷一下是否滿了
//順序表頭插
void SeqListPushFront(SL* ps, SLDateType x)
{
//先判斷滿了沒有
SeqListCheckCapacity(ps);
int i = ps->size;
while(i > 0)
{
ps->a[i] = ps->a[i - 1];
i--;
}
ps->a[0] = x;
ps->size++;
}
2.7 順序表尾刪
很簡單，只要把size往前移動一位就行
注意判斷size有沒有刪到0
//順序表尾刪
void SeqListPopFront(SL* ps)
{
assert(ps->size > 0);
ps->size--;
}
2.8 順序表頭刪
和頭插類似
//順序表頭刪
void SeqListPopBack(SL* ps)
{
assert(ps->size > 0);
int i = 0;
for (i = 0; i < ps->size; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->size--;
}
2.9 順序表查找
簡單的陣列中尋找數字
// 順序表查找
int SeqListFind(SL* ps, SLDateType x)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (x == ps->a[i])
{
printf("找到了");
}
}
}
3.0 順序表中間插入
其實就比順序表頭插多一個判斷，pos有無超出順序表范圍
// 順序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDateType x)
{
//判斷是否超過鏈表范圍
assert(pos >= 0 && pos <= ps->size);
//先判斷滿了沒有
SeqListCheckCapacity(ps);
int i = ps->size;
while (i > pos)
{
ps->a[i] = ps->a[i - 1];
i--;
}
ps->a[pos] = x;
ps->size++;
}
3.1 順序表中間洗掉
其實也和頭刪是一個道理
注意邊界位置
// 順序表洗掉pos位置
void SeqListErase(SL* ps, int pos)
{
assert(pos > 0 && pos <= ps->size);
int i = 0;
for (i = pos - 1; i < ps->size - 1; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->size--;
}
3.2 測驗
#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
void test7()
{
SL s1;
//初始化順序表
SeqListInit(&s1);
//尾插
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
//列印順序表
SeqListPrint(&s1);
//在指定位置洗掉
SeqListErase(&s1, 1);
SeqListErase(&s1, 2);
SeqListErase(&s1, 2);
//列印順序表
SeqListPrint(&s1);
}
void test6()
{
SL s1;
//初始化順序表
SeqListInit(&s1);
//尾插
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
//列印順序表
SeqListPrint(&s1);
//1后面插入1
SeqListInsert(&s1, 1, 1);
//4后面插入2
SeqListInsert(&s1, 4, 2);
//1前面插入5
SeqListInsert(&s1, 0, 5);
//列印順序表
SeqListPrint(&s1);
}
void test5()
{
SL s1;
//初始化順序表
SeqListInit(&s1);
//尾插
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
//列印順序表
SeqListPrint(&s1);
SeqListFind(&s1, 2);
}
void test4()
{
SL s1;
//初始化順序表
SeqListInit(&s1);
//尾插
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
//列印順序表
SeqListPrint(&s1);
//順序表頭刪
SeqListPopBack(&s1);
SeqListPopBack(&s1);
//列印順序表
SeqListPrint(&s1);
}
void test3()//測驗尾刪
{
SL s1;
//初始化順序表
SeqListInit(&s1);
//尾插
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
//列印順序表
SeqListPrint(&s1);
//尾刪
SeqListPopFront(&s1);
SeqListPopFront(&s1);
//列印順序表
SeqListPrint(&s1);
}
void test2()//測驗頭插
{
SL s1;
//初始化順序表
SeqListInit(&s1);
//尾插
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
//頭插
SeqListPushFront(&s1, 1);
SeqListPushFront(&s1, 2);
//列印順序表
SeqListPrint(&s1);
}
void test1()//測驗尾插
{
SL s1;
//初始化順序表
SeqListInit(&s1);
//尾插
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
//列印順序表
SeqListPrint(&s1);
}
void print_menu()//簡陋一點
{
printf(" 1.測驗尾插 2.測驗頭插 3.測驗尾刪\n");
printf(" 4.測驗頭刪 5.測驗查找 6.測驗中間插入 7.測驗中間洗掉\n");
}
int main()
{
SL s1;
//初始化順序表
SeqListInit(&s1);
int input = 1;
while (input)
{
print_menu();//列印選單
scanf("%d", &input);
switch (input)
{
case 1:
test1();//測驗尾插
break;
case 2:
test2();
break;
case 3:
test3();
break;
case 4:
test4();
break;
case 5:
test5();
break;
case 6:
test6();
break;
case 7:
test7();
break;
case 0:
//銷毀順序表
SeqListDestory(&s1);
break;
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/321235.html
標籤：其他
下一篇：資料結構初階：演算法復雜度