- 整體思路:
- 動態順序表的增刪查改等:
- (1)初始化:
- (2) 尾插
- 增容
- (3) 尾刪
- (4)頭插
- (5)頭刪
- (6)查找
- (7)在pos下標后進行插入
- (7)在pos下標后進行洗掉
- 整體代碼
- 1.SeqList.h
- 2.SeqList.c
- 3.test.c
整體思路:
要知道我們實作資料結構,是要理解他是有什么用處的,
順序表就是連續存盤資料,它可以實作增刪查改,讓我們的資料變得靈活可變,讓我們能夠靈活的使用資料,
順序表有兩個型別:一個是靜態的順序表,一個是動態的順序表,他們都有各自的優點和缺點,我們這次是采取工程檔案的形式,
靜態版本:就是順序表的大小是確定的,不管你的資料是多少,容量是固定的,在定義的是時候是這樣的:
#define MAX 1000//設定最大容量為100.
//為什么要宏呢?
//因為我們后面會多次用到容量為1000,我們就直接都用MAX代替
//以防我們需要修改容量大小時候所以的1000都要修改,
//進行宏替換只需要修改宏中的數字就可,
tpyedef int STDataType;//重命名,后面要用到其他資料型別就可以在這里直接改變,
typedef struct SeqList
{
STDataType data[MAX];//順序表存盤的位置
int size;//記錄已經存盤的個數
}SL;
我這次主要介紹的是動態的版本,應為大部分的資料都是多變的,所以動態版本是更好的,
tpyedef int STDataType;//重命名,后面要用到其他資料型別就可以在這里直接改變,
typedef struct SeqList
{
STDataType* a;//這里用動態申請空間
int size;//資料個數
int capacity//動態順序表的容量,用來判斷是否需要增容,
}SL;
動態順序表的增刪查改等:
這些函式的定義是要放在頭檔案里面的,實作是放在一個.c檔案中的:
(1)初始化:
一開始順序表是什么都沒有的,為空
//實作:
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;
}
(2) 尾插
尾插就是在順序表的最后面進行資料的插入,每當我們插入的時候都需要進行判斷順序表是否需要增容,以及后面的頭插和在任何位置插入,都需要進行判斷是否需要增容,所以為了防止代碼的重復,我們直接封裝一個增容函式,
增容
void SeqListCheckCapacity(SL* ps)//判斷是否需要增容
{
if (ps->size == ps->capacity)
{
//判斷ps->capacity是否為0.
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//進行增容,realloc中第一個人引數如果為NULL,則效果相當于malloc,第二個引數是位元組數,
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
printf("Realloc Failed");
exit(-1);//例外退出,終止程式,
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
這樣我們就可以尾插了:
void SeqListPushBack(SL* ps, SLDataType x)//尾插
{
//1.判斷是否要增容
SeqListCheckCapacity(ps);
//2.空間足夠,進行尾插
ps->a[ps->size] = x;
ps->size++;
}
(3) 尾刪
每當洗掉的時候都要判斷順序表中是否還有資料,如果有資料才能洗掉,沒有資料是不能洗掉的,
void SeqListPopBack(SL* ps)//尾刪
{
if (ps->size != 0)//沒有資料可以刪了就進不去
{
ps->size--;
}
}
(4)頭插
頭插的時候,因為資料是連續的,所以我們必須要把所以的資料從后往前一次向后挪動一個位置,所以時間復雜度是O(n),這也是順序表的一個缺陷,
void SeqListPushFront(SL* ps, SLDataType x)//頭插
{
//1.判斷是否要增容
SeqListCheckCapacity(ps);
//2.進行頭插
int end = ps->size - 1;
//挪資料
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
(5)頭刪
頭刪也是跟頭插類似,要把除了第一個資料以為從第二個資料開始依次覆寫資料:
void SeqListPopFornt(SL* ps)//頭刪
{
if (ps->size > 0)
{
int begin = 0;
for (begin; begin < ps->size - 1; begin++)
{
ps->a[begin] = ps->a[begin + 1];
}
ps->size--;
}
}
(6)查找
查找就是輸入一個資料,如果找到這個資料就回傳資料的下標,找不到就回傳-1,從而告訴我們沒有這個資料,
int SeqListFind(const SL* ps, SLDataType x)
//查找,找到回傳下標,找不到回傳-1
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
(7)在pos下標后進行插入
void SeqListInsert(SL* ps, int pos, SLDataType x)//在pos下標后進行插入
{
//1.判斷pos是否小于ps->size或者小于0
if (pos < ps->size && pos >= 0)
{
//(1).判斷是否需要增容
SeqListCheckCapacity(ps);
//(2).插入
int end = ps->size ;
while (end > pos)
{
ps->a[end] = ps->a[end - 1];
end--;
}
ps->a[pos + 1] = x;
ps->size++;
}
//用錯了回傳
else
{
//給定的下標不合法我們就直接斷言報錯
assert(pos >= 0 && pos < ps->size);
}
}
(7)在pos下標后進行洗掉
void SeqListErase(SL* ps, int pos)//洗掉下標為pos的值
{
if (pos >= 0 && pos < ps->size)
{
int begin = pos;
while (begin < ps->size - 1)
{
ps->a[begin] = ps->a[begin + 1];
begin++;
}
ps->size--;
}
}
整體代碼
1.SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//#define N 100
//typedef int SLDataType;
//
靜態順序表
//typedef struct SeqList
//{
// SLDataType a[N];
// int size;//表示順序表存盤元素的個數
//}SL;
//
介面函式
//void SeqListInit(SL* ps);//初始化
//
//void SeqListPushBack(SL* ps, SLDataType x);//尾插
//void SeqListPopBack(SL* ps);//尾刪
//void SeqListPushFront(SL* ps, SLDataType x);//頭插
//void SeqListPopFornt(SL* ps, SLDataType x);//頭刪
typedef int SLDataType;
//動態順序表
typedef struct SeqList
{
SLDataType* a;
int size;//表示順序表存盤元素的個數
int capacity; //陣列實際能存盤空間的容量的個數,
}SL;
//介面函式(增刪查改)
void SeqListInit(SL* ps);//初始化
void SeqListDestroy(SL* ps);//銷毀
void SeqListCheckCapacity(SL* ps);//判斷是否需要增容
void SeqListPushBack(SL* ps, SLDataType x);//尾插
void SeqListPopBack(SL* ps);//尾刪
void SeqListPushFront(SL* ps, SLDataType x);//頭插
void SeqListPopFornt(SL* ps);//頭刪
void SeqListPrint(const SL* ps);//列印
int SeqListFind(const SL* ps, SLDataType x);//查找,找到回傳下標,找不到回傳-1
void SeqListInsert(SL* ps, int pos, SLDataType x);//在pos下標后進行插入
void SeqListErase(SL* ps, int pos);//洗掉下標為pos的值
2.SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListCheckCapacity(SL* ps)//判斷是否需要增容
{
if (ps->size == ps->capacity)
{
//判斷ps->capacity是否為0.
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//進行增容,realloc中第一個人引數如果為NULL,則效果相當于malloc,第二個引數是位元組數,
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
printf("Realloc Failed");
exit(-1);//例外退出,終止程式,
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
void SeqListPrint(const SL* ps)//列印
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
void SeqListInit(SL* ps)//初始化
{
ps->a = NULL;
ps->size = ps->capacity = 0;
}
void SeqListDestroy(SL* ps)//銷毀
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
void SeqListPushBack(SL* ps, SLDataType x)//尾插
{
//1.判斷是否要增容
SeqListCheckCapacity(ps);
//2.空間足夠,進行尾插
ps->a[ps->size] = x;
ps->size++;
}
void SeqListPopBack(SL* ps)//尾刪
{
if (ps->size != 0)//沒有資料可以刪了就進不去
{
ps->size--;
}
}
void SeqListPushFront(SL* ps, SLDataType x)//頭插
{
//1.判斷是否要增容
SeqListCheckCapacity(ps);
//2.進行頭插
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
void SeqListPopFornt(SL* ps)//頭刪
{
if (ps->size > 0)
{
int begin = 0;
for (begin; begin < ps->size - 1; begin++)
{
ps->a[begin] = ps->a[begin + 1];
}
ps->size--;
}
}
int SeqListFind(const SL* ps, SLDataType x)//查找,找到回傳下標,找不到回傳-1
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
void SeqListInsert(SL* ps, int pos, SLDataType x)//在pos下標后進行插入
{
//1.判斷pos是否小于ps->size或者小于0
if (pos < ps->size && pos >= 0)
{
//(1).判斷是否需要增容
SeqListCheckCapacity(ps);
//(2).插入
int end = ps->size ;
while (end > pos)
{
ps->a[end] = ps->a[end - 1];
end--;
}
ps->a[pos + 1] = x;
ps->size++;
}
//用錯了回傳
else
{
assert(pos >= 0 && pos < ps->size);
}
}
void SeqListErase(SL* ps, int pos)//洗掉下標為pos的值
{
if (pos >= 0 && pos < ps->size)
{
int begin = pos;
while (begin < ps->size - 1)
{
ps->a[begin] = ps->a[begin + 1];
begin++;
}
ps->size--;
}
}
3.test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void TestSeqList1()
{
SL s1;
SeqListInit(&s1);
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
SeqListPushBack(&s1, 5);
SeqListPrint(&s1);
SeqListDestroy(&s1);
}
void TestSeqList2()
{
SL s1;
SeqListInit(&s1);
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPrint(&s1);
SeqListPushFront(&s1, 0);
SeqListPushFront(&s1, -1);
SeqListPushFront(&s1, -2);
SeqListPushFront(&s1, -3);
SeqListPopFornt(&s1);
SeqListPrint(&s1);
SeqListDestroy(&s1);
}
void TestSeqList3()
{
SL s1;
SeqListInit(&s1);
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListInsert(&s1, 1, 10);
SeqListInsert(&s1, 1, 20);
SeqListInsert(&s1, 1, 30);
SeqListPrint(&s1);
SeqListErase(&s1, 5);
SeqListPrint(&s1);
SeqListDestroy(&s1);
}
void menu()
{
printf("********************************************\n");
printf("************ 請選擇 ***********\n");
printf("**** 1.頭插 2.尾插 ****\n");
printf("**** 3.頭刪 4.尾刪 ****\n");
printf("**** 5.列印 -1.退出 ****\n");
printf("********************************************\n");
printf("********************************************\n");
}
void Test()
{
int input;
int x;
SL s1;
SeqListInit(&s1);
printf("please Select\n");
do
{
menu();
scanf("%d", &input);
switch (input)
{
case 1:
printf("Please enter the contents of the header to end with-1\n");
scanf("%d", &x);
while (x != -1)
{
SeqListPushFront(&s1, x);
scanf("%d", &x);
}
break;
case 2:
printf("Please enter the contents of the tail insert ending in-1\n");
scanf("%d", &x);
while (x != -1)
{
SeqListPushBack(&s1, x);
scanf("%d", &x);
}
break;
case 3:
SeqListPopFornt(&s1);
printf("Pop successful\n");
break;
case 4:
SeqListPopBack(&s1);
printf("Pop successful\n");
break;
case 5:
SeqListPrint(&s1);
break;
case -1:
exit(0);
break;
default:
printf("Selected error!\n");
break;
}
} while (input != -1);
SeqListDestroy(&s1);
}
int main()
{
//menu() ;
//TestSeqList1();
//TestSeqList2();
//TestSeqList3();
Test();
return 0;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/335548.html
標籤:其他
上一篇:Dart對串列進行排序
下一篇:作業系統存盤管理
