目錄
概念及結構
介面實作
順序表初始化
檢查空間(動態)
順序表尾插
順序表頭插
順序表尾刪
順序表頭刪
順序表查找
順序表在pos位置插入x
順序表洗掉pos位置的值
順序表銷毀(動態)
順序表列印
通訊錄實作
Contact.h
Contact.c
test.c
順序表的問題及思考
概念及結構
順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構,一般情況下采用陣列存盤,在陣列上完成資料的增刪查改,
順序表一般可以分為:
- 靜態順序表:使用定長陣列儲存元素,

- 動態順序表:使用動態開辟的陣列儲存,

介面實作
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLDataType;
//順序表的靜態儲存
//#define MAX 100 //靜態通訊錄總容量
//typedef struct SeqList
//{
// SLDataType array[MAX];
// size_t size;
//}SeqList;
// 順序表的動態存盤
#define N 5 //第一次開辟容量大小
typedef struct SeqList
{
SLDataType* array; // 指向動態開辟的陣列
size_t size ; // 有效資料個數
size_t capicity ; // 容量空間的大小
}SeqList;
// 基本增刪查改介面
// 順序表初始化
void SeqListInit(SeqList* ps);
// 檢查空間,如果滿了,進行增容
void CheckCapacity(SeqList* ps);
// 順序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x);
// 順序表尾刪
void SeqListPopBack(SeqList* ps);
// 順序表頭插
void SeqListPushFront(SeqList* ps, SLDataType x);
// 順序表頭刪
void SeqListPopFront(SeqList* ps);
// 順序表查找
int SeqListFind(SeqList* ps, SLDataType x);
// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x);
// 順序表洗掉pos位置的值
void SeqListErase(SeqList* ps, size_t pos);
// 順序表銷毀
void SeqListDestory(SeqList* ps);
// 順序表列印
void SeqListPrint(SeqList* ps);
順序表初始化
靜態版:因為在定義結構體時已經創建了固定容量的陣列,所以在初始化時只需要將陣列元素置為 0,再將有效元素個數置為0即可,
動態版:在創建結構體時結構體成員中只創建了指向順序表的指標,并沒有創建空間,所以在初始化時可以使用兩種方法初始化:
- 初始化時創建一定容量的空間,當然在后面空間檢查時會有一些變化,
- 初始化時不創建空間,將指標置為空,
這里我們使用第二種方法:
//靜態版
void SeqListInit(SeqList* ps)
{
memset(ps->array,0,sizeof(ps->array[0])*N);//將陣列所有元素置為0
ps->size = 0;//陣列中的有效元素置為0
}
//動態版
void SeqListInit(SeqList* ps)
{
ps->a = NULL;//將指向陣列的指標置為空
ps->capacity = 0;//陣列容量為0
ps->size = 0;//陣列中的有效元素為0
}
檢查空間(動態)
空間檢查只會在動態版中有,靜態順序表的空間大小是固定的,不需要擴容,容量滿了之后不能插入元素,
void CheckCapacity(SeqList* ps)
{
if (ps->capacity == ps->size)//當空間容量和有效元素相等時才需要增容
{
if (ps->capacity == 0)//當空間容量為0時
{
ps->a = (SLDataType*)malloc(sizeof(SLDataType) * N);
if (ps->a == NULL)
{
printf("malloc erro");//開辟失敗
exit(-1);
}
ps->capacity = N;
}
else
{
SLDataType* tmp = (SLDataType*)realloc(ps->a ,sizeof(SLDataType) * ps->capacity * 2);//空間容量不夠時
if (tmp == NULL)
{
printf("realloc erro");
exit(-1);
}
ps->a = tmp;
ps->capacity *= 2;//增容2倍
}
}
順序表尾插
尾插即在順序表的最后一個有效元素的后面一個位置插入,
void SeqListPushBack(SeqList* ps, SLDataType x)
{
SeqListCheckCapacity(ps);//插入元素時需先檢查容量是否足夠
ps->a[ps->size] = x;//直接在最后插入即可
ps->size++;//有效元素增加1
}
順序表頭插
頭插即在順序表的第一個位置插入元素,但第一個位置是有元素的,所以需要將順序表中所有元素向后移動一個位置,
void SeqListPushFront(SeqList* ps, SLDataType x)
{
SeqListCheckCapacity(ps);//空間檢查
//1.可直接使用memmove移動
memmove(ps->a + 1, ps->a, sizeof(SLDataType) * ps->size);
//2.依次移動
int i = 0;
for(i = ps->size; i>0; i--)//注意陣列不要越界
{
ps->array[i] = ps->array[i-1];
}
ps->a[0] = x;//在第一個位置插入
ps->size++;
}
順序表尾刪
直接洗掉最后一個元素,并將有效元素個數減一即可,
void SeqListPopBack(SeqList* ps)
{
assert(ps->size > 0);//洗掉必須保證陣列中有有效元素
ps->size --;//直接將有效元素個減1即可
} //注:不要將該位置置為0,因為可能該位置處原來放的就是0
順序表頭刪
洗掉第一個元素,再將剩余元素像左移動一個位置,
void SeqListPopFront(SeqList* ps)
{
assert(ps->size > 0);//同樣洗掉需保證陣列中存在有效元素
//1.通過memmove移動
memmove(ps->a, ps->a + 1, sizeof(SLDataType) * (ps->size - 1));
//2.依次移動
int i = 0;
for(i = 0; i < ps->szie-1; i++)
{
ps->array[i] = ps->array[i+1];
}
ps->size--;//元素個數減1
}
順序表查找
int SeqListFind(SeqList* ps, SLDataType x)
{
int i = 0;
for (i = 0; i < ps->size; i++)//因為不確定陣列中的元素是否排序,所以只能依次查找
{
if (ps->a[i] == x)
{
return i;//找到回傳該元素在陣列中的下標
//注:這里沒有考慮重復元素的情況
}
}
return -1;//未找到回傳-1;
}
順序表在pos位置插入x
將指定位置處向右所有的元素向后移動一個位置,將x插入下標為pos位置處,
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
SeqListCheckCapacity(ps);//同樣增加元素需先檢查容量
//保證輸入的下標是有效的
//1.溫柔方法
if (pos > ps->size || pos < 0)
{
printf("輸入位置資訊錯誤\n");
return;
}
//2.暴力方法
//assert(pos <= ps->size && pos >= 0)
//將該位置和該位置以后的元素向后移動一個空間
int i = 0;
for (i = ps->size - 1; i >= pos; i--)
{
ps->a[i + 1] = ps->a[i];
}
ps->a[pos] = x;
ps->size++;
}
順序表洗掉pos位置的值
同理,將pos位置處右邊所有元素向左移動一個位置,覆寫pos位置處的值,
void SeqListErase(SeqList* ps, int pos)
{
assert(ps->size > 0 && pos >= 0 && pos < ps->size - 1);//保證陣列中的有效元素不為0,且輸入的下標有效
int i = 0;
for (i = pos + 1; i < ps->size; i++)//將該位置以后的元素向前移動一個位置,將該位置覆寫
{
ps->a[i - 1] = ps->a[i];
}
ps->size--;
}
順序表銷毀(動態)
動態創建的空間在程式結束后必須將該空間釋放,不然會導致記憶體泄漏,
void SeqListDestory(SeqList* ps)
{
free(ps->a);//釋放開辟的空間
ps->a = NULL;//指標置為空
ps->capacity = ps->size = 0;//空間容量和有效元素都置為0
}
順序表列印
void SeqListPrint(SeqList* ps)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
通訊錄實作
Contact.h
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define NAME_MAX 10
#define ADDR_MAX 10
#define TELE_MAX 12
#define CONTACT_MAX 1000
#define CAPACITY 3
struct PeopleInfo
{
char name[NAME_MAX];
int age;
char addr[ADDR_MAX];
char tele[TELE_MAX];
};
//靜態
//struct Contact
//{
// struct PeopleInfo data[CONTACT_MAX];
// int size;
//};
//動態
struct Contact
{
struct PeopleInfo* data;
int size;//通訊錄中有效元素個數
int capacity;//通訊錄容量
};
//初始化通訊錄
void InitContact(struct Contact* pc);
//通訊錄擴容
void BuyContact(struct Contact* pc);
//增加聯系人
void AddContact(struct Contact* pc);
//洗掉聯系人
void DelContact(struct Contact* pc);
//查找聯系人
void SearchContact(const struct Contact* pc);
//修改聯系人
void ModifyContact(struct Contact* pc);
//排序通訊錄串列(姓名)
void SortContact(struct Contact* pc);
//顯示通訊錄
void ShowContact(const struct Contact* pc);
//銷毀通訊錄
void DestoryContact(struct Contact* pc);
//保存資訊到通訊錄中
void SaveContact(struct Contact* pc);
//加載檔案中的資訊到通訊錄中
void LoadContact(struct Contact* pc);
Contact.c
#include"Contact.h"
//通訊錄擴容
void BuyContact(struct Contact* pc)
{
if (pc->size == pc->capacity)
{
struct PeopleInfo* tmp = (struct PeopleInfo*)realloc(pc->data, sizeof(struct PeopleInfo) * (pc->capacity) * 2);
if (tmp == NULL)
{
perror("BuyContact::fail");
return;
}
pc->data = tmp;
pc->capacity *= 2;
printf("增容成功\n");
}
}
void LoadContact(struct Contact* pc)
{
//打開檔案
FILE* pf = fopen("Contact.txt", "rb");
if (pf == NULL)
{
perror("LoadContact::fopen");
return;
}
//讀檔案
struct PeopleInfo tmp = { 0 };
while (fread(&tmp, sizeof(struct PeopleInfo), 1, pf))
{
BuyContact(pc);
pc->data[pc->size] = tmp;
pc->size++;
}
//關閉檔案
fclose(pf);
pf = NULL;
}
//初始化通訊錄(靜態)
//void InitContact(struct Contact* pc)
//{
// memset(pc->data, 0, sizeof(struct PeopleInfo) * CONTACT_MAX);
// pc->size = 0;
//}
//初始化通訊錄(動態)
void InitContact(struct Contact* pc)
{
pc->data = (struct PeopleInfo*)malloc(sizeof(struct PeopleInfo) * CAPACITY);
pc->capacity = CAPACITY;
pc->size = 0;
//加載檔案資訊到通訊錄
LoadContact(pc);
}
//添加聯系人
void AddContact(struct Contact* pc)
{
//靜態
/*if (pc->size >= CONTACT_MAX)
{
printf("通訊錄已滿\n");
return;
}*/
//動態(通訊錄滿了需增容)
BuyContact(pc);
printf("請輸入名字>");
scanf("%s", pc->data[pc->size].name);
printf("請輸入年齡>");
scanf("%d", &(pc->data[pc->size].age));
printf("請輸入住址>");
scanf("%s", pc->data[pc->size].addr);
printf("請輸入電話>");
scanf("%s", pc->data[pc->size].tele);
printf("添加成功!\n");
pc->size++;
}
//顯示通訊錄串列
void ShowContact(const struct Contact* pc)
{
if (pc->size == 0)
{
printf("通訊錄為空\n");
exit(1);
}
printf("\t%-10s\t%-3s\t%-10s\t%-12s\n", "name", "age", "addr", "tele");
int i = 0;
for (i = 0; i < pc->size; i++)
{
printf("\t%-10s\t%-3d\t%-10s\t%-12s\n",
pc->data[i].name,
pc->data[i].age,
pc->data[i].addr,
pc->data[i].tele);
}
}
int FindByName(const struct Contact* pc,const char*name)
{
int i = 0;
for (i = 0; i < pc->size; i++)
{
if (strcmp(pc->data[i].name, name) == 0)
{
return i;
}
}
return -1;
}
//洗掉聯系人
void DelContact(struct Contact* pc)
{
if (pc->size <= 0)
{
printf("通訊錄為空\n");
return;
}
char name[NAME_MAX] = { 0 };
printf("請輸入需要洗掉的聯系人>");
scanf("%s", name);
int i = FindByName(pc,name);
if (i != -1)
{
for (; i < pc->size - 1; i++)
{
pc->data[i] = pc->data[i + 1];
}
pc->size--;
printf("洗掉成功\n");
}
else
{
printf("無此聯系人\n");
}
}
//查找聯系人
void SearchContact(const struct Contact* pc)
{
char name[NAME_MAX] = { 0 };
printf("請輸入需要查找的聯系人>");
scanf("%s", name);
int i = FindByName(pc, name);
if(i!=-1)
{
printf("\t%-10s\t%-3s\t%-10s\t%-12s\n", "name", "age", "addr", "tele");
printf("\t%-10s\t%-3d\t%-10s\t%-12s\n",
pc->data[i].name,
pc->data[i].age,
pc->data[i].addr,
pc->data[i].tele);
}
else
{
printf("無此聯系人\n");
}
}
//修改聯系人
void ModifyContact(struct Contact* pc)
{
char name[NAME_MAX] = { 0 };
printf("請輸入需要修改的聯系人>");
scanf("%s", name);
int i = FindByName(pc, name);
if (i != -1)
{
printf("請輸入修改后的名字>");
scanf("%s", pc->data[i].name);
printf("請輸入修改后的年齡>");
scanf("%d", &(pc->data[i].age));
printf("請輸入修改后的住址>");
scanf("%s", pc->data[i].addr);
printf("請輸入修改后的電話>");
scanf("%s", pc->data[i].tele);
}
else
{
printf("無此聯系人\n");
}
}
//排序通訊錄串列(姓名)
int cmp_name(const void* a, const void* b)
{
return strcmp(((struct PeopleInfo*)a)->name , ((struct PeopleInfo*)b)->name);
}
void SortContact(struct Contact* pc)
{
qsort(pc->data, pc->size, sizeof(struct PeopleInfo), cmp_name);
printf("排序成功\n");
}
//銷毀通訊錄
void DestoryContact(struct Contact* pc)
{
free(pc->data);
pc->data = NULL;
pc->capacity = 0;
pc->size = 0;
}
//保存資訊到通訊錄中
void SaveContact(struct Contact* pc)
{
//打開檔案
FILE* pf = fopen("Contact.txt", "w");
if (pf == NULL)
{
perror("SaveContact::fopen");
exit(1);
}
//寫檔案
int i = 0;
for (i = 0; i < pc->size; i++)
{
fwrite(&(pc->data[i]), sizeof(struct PeopleInfo), 1, pf);
}
//關閉檔案
fclose(pf);
pf = NULL;
}
test.c
#include"Contact.h"
void menu()
{
printf("******************************\n");
printf("******* 1.add 2.del *******\n");
printf("******* 3.search 4.modify ****\n");
printf("******* 5.sort 6.show ******\n");
printf("********* 0.exit *************\n");
printf("******************************\n");
}
enum contact
{
EXIT,
ADD,
DEL,
SEARCH,
MODIFY,
SORT,
SHOW
};
int main()
{
//創建通訊錄
struct Contact con;
//初始化通訊錄
InitContact(&con);
int input = 0;
do
{
menu();
printf("請選擇功能>");
scanf("%d", &input);
switch (input)
{
case EXIT:
//保存資訊
SaveContact(&con);
DestoryContact(&con);
printf("退出通訊錄\n");
break;
case ADD:
AddContact(&con);
break;
case DEL:
DelContact(&con);
break;
case SEARCH:
SearchContact(&con);
break;
case MODIFY:
ModifyContact(&con);
break;
case SORT:
SortContact(&con);
break;
case SHOW:
ShowContact(&con);
break;
default:
printf("選擇錯誤,請重新輸入\n");
break;
}
} while (input);
return 0;
}
順序表的問題及思考
問題:
1. 中間/頭部的插入洗掉,時間復雜度為O(N)
2. 增容需要申請新空間,拷貝資料,釋放舊空間,會有不小的消耗,
3. 增容一般是呈2倍的增長,勢必會有一定的空間浪費,例如當前容量為100,滿了以后增容到200,我們再繼續插入了5個資料,后面沒有資料插入了,那么就浪費了95個資料空間,
思考:如何解決以上問題呢?
我們下期再來解答~
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/323440.html
標籤:其他
