目錄
1.順序表的概念及結構
1.1 線性表
如何理解邏輯結構和物理結構?
1.2 順序表分類
順序表和數組的區別:
順序表分類:
靜態順序表
動態順序表
1.3 動態順序表的實現
初始化
尾插
頭插
尾刪
頭刪
在指定位置之前插入數據
刪除指定位置的數據
順序表的查找
最終代碼:
test.c
SeqList.h
SeqList.c
2.順序表實現通訊錄
2.1?基于動態順序表實現通訊錄
2.1.1 功能要求
2.2 代碼的實現:
1.建立五個文件
2.將順序表結構體的類型,int改為通訊錄結構體自定義類型
順序表
通訊錄
3.給通訊錄結構體改名為typedef SL contact
4.對于SeqList.h和Contact.h頭文件包含的處理
5.列出通訊錄的功能
6.通訊錄的初始化和銷毀
7.通訊錄的添加數據
8.通訊錄刪除
9.展示通訊錄數據
10.通訊錄的修改和查找
11.打印菜單
最終代碼
test.c
Contact.h
Contact.c
1.順序表的概念及結構
1.1 線性表
線性表(linear list)是n個具有相同特性的數據元素的有限序列。線性表是?種在實際中?泛使?的數據結構,常?的線性表:順序表、鏈表、棧、隊列、字符串...線性表在邏輯上是線性結構,也就說是連續的?條直線。但是在物理結構上并不?定是連續的,線性表在物理上存儲時,通常以數組和鏈式結構的形式存儲。案例:蔬菜分為綠葉類、?類、菌菇類。線性表指的是具有部分相同特性的?類數據結構的集合
如何理解邏輯結構和物理結構?
物理結構:在內存中存儲的形式,不一定連續
邏輯結構:肉眼可以看到的,我們想象出來的數據結構,人為想象的,連續的
順序表是物理結構和邏輯結構都連續的一種線性表
1.2 順序表分類
順序表和數組的區別:
順序表的底層結構是數組,對數組的封裝,實現了常?的增刪改查等接?
順序表分類:
靜態順序表
概念:使?定?數組存儲元素
靜態順序表缺陷:空間給少了不夠?,給多了造成空間浪費
動態順序表
1.3 動態順序表的實現
初始化
尾插
頭插
尾刪
頭刪
在指定位置之前插入數據
刪除指定位置的數據
順序表的查找
最終代碼:
test.c
#include"SeqList.h"void SLTest01()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(sl);//1 2 3 4//SLPushFront(&sl, 5);//SLPushFront(&sl, 6);SLPopBack(&sl);SLPrint(sl);//1 2 3 SLPopBack(&sl);SLPrint(sl);SLPopBack(&sl);SLPrint(sl);SLPopBack(&sl);SLPrint(sl);SLPopFront(&sl);SLPrint(sl);//...........SLDestroy(&sl);
}void SLTest02()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(sl);//1 2 3 4//測試指定位置之前插入數據//SLInsert(&sl, 1, 99);//SLInsert(&sl, sl.size, 88);//測試刪除指定位置的數據//SLErase(&sl, 1);//SLPrint(sl);//1 3 4//測試順序表的查找int find = SLFind(&sl, 40);if (find < 0){printf("沒有找到!\n");}else {printf("找到了!下標為%d\n",find);}SLDestroy(&sl);
}int main()
{SLTest01();SLTest02();return 0;
}
SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定義順序表的結構//#define N 100
//
////靜態順序表
//struct SeqList
//{
// int arr[N];
// int size;//有效數據個數
//};typedef int SLDataType;
//動態順序表
typedef struct SeqList
{SLDataType* arr;int size; //有效數據個數int capacity; //空間大小
}SL;//typedef struct SeqList SL;//順序表初始化
void SLInit(SL* ps);
//順序表的銷毀
void SLDestroy(SL* ps);
void SLPrint(SL s);//頭部插入刪除 / 尾部插入刪除
void SLPushBack(SL* ps, SLDataType x);//尾插
void SLPushFront(SL* ps, SLDataType x);//頭插void SLPopBack(SL* ps);//尾刪
void SLPopFront(SL* ps);//頭刪//指定位置之前插入/刪除數據
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);
SeqList.c
#include"SeqList.h"
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}
//順序表的銷毀
void SLDestroy(SL* ps)
{if (ps->arr) //等價于 if(ps->arr != NULL){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)
{//插入數據之前先看空間夠不夠if (ps->capacity == ps->size){//申請空間//malloc calloc realloc int arr[100] --->增容realloc//三目表達式int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申請多大的空間if (tmp == NULL){perror("realloc fail!");exit(1);//直接退出程序,不再繼續執行}//空間申請成功ps->arr = tmp;ps->capacity = newCapacity;}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{////溫柔的解決方式//if (ps == NULL)//{// return;//}assert(ps); //等價與assert(ps != NULL)//ps->arr[ps->size] = x;//++ps->size;SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}
//頭插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//先讓順序表中已有的數據整體往后挪動一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];//arr[1] = arr[0]}ps->arr[0] = x;ps->size++;
}void SLPrint(SL s)
{for (int i = 0; i < s.size; i++){printf("%d ", s.arr[i]);}printf("\n");
}
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//順序表不為空//ps->arr[ps->size - 1] = -1;--ps->size;
}
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);//數據整體往前挪動一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1]; //arr[size-2] = arr[size-1]}ps->size--;
}//在指定位置之前插入數據
// 1 2 size = 2
//pos 0 -1 100000
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//插入數據:空間夠不夠SLCheckCapacity(ps);//讓pos及之后的數據整體往后挪動一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];//arr[pos+1] = arr[pos]}ps->arr[pos] = x;ps->size++;
}
//刪除指定位置的數據
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
//查找
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){//找到啦return i;}}//沒有找到return -1;
}
2.順序表實現通訊錄
2.1?基于動態順序表實現通訊錄
C語?基礎要求:結構體、動態內存管理、順序表、?件操作
2.1.1 功能要求
1)?少能夠存儲100個?的通訊信息
2)能夠保存??信息:名字、性別、年齡、電話、地址等
3)增加聯系?信息
4)刪除指定聯系?
5)查找制定聯系?
6)修改指定聯系?
7)顯?聯系?信息
2.2 代碼的實現:
1.建立五個文件
分別為SeqList.c和SeqList.h,這兩個是通訊錄的底層文件;Contact.c和Contact.h,這兩個函數是通訊錄的實現文件;test.c是測試函數
2.將順序表結構體的類型,int改為通訊錄結構體自定義類型
順序表
SeqList.h
通訊錄
Contact.h
3.給通訊錄結構體改名為typedef SL contact
4.對于SeqList.h和Contact.h頭文件包含的處理
因為SeqList.h中包含了Contact.h所以可以直接使用重命名peoInfo
因為Contact.h沒有包含SeaList.h所以找不到順序表的結構體,但是SeqList.h已經包含了Contact.h不能相互包含頭文件,會報錯,所以要在Contact.h前置聲明struct SeqList;所以typedef struct SeqList Contact;這樣才能找到SL
由以上兩步通訊錄的實現和順序表有了連接
5.列出通訊錄的功能
6.通訊錄的初始化和銷毀
在Contact.c包含頭文件SeqList.h
通訊錄的初始化和銷毀就是順序表的初始化和銷毀
測試,通過調試觀察
7.通訊錄的添加數據
將姓名、性別、年齡、電話號碼、地址儲存進通訊錄的結構體,注意:只要年齡是int類型的,所以要&,其他的都是數組,數組名表示首元素地址;然后調用頭插/尾插函數(自定義都能實現)
測試,通過調試觀察
8.通訊錄刪除
通訊錄的刪除就是順序表的刪除,調用順序表的刪除函數,調用指定刪除函數,不是頭刪也不是尾刪
測試,通過調試觀察
9.展示通訊錄數據
測試,直接打印
10.通訊錄的修改和查找
測試,直接打印
11.打印菜單
最終代碼
test.c
#include"SeqList.h"void menu()
{printf("******************通訊錄******************\n");printf("*******1.增加聯系人 2.刪除聯系人********\n");printf("*******3.修改聯系人 4.查找聯系人********\n");printf("*******5.展示聯系人 0. 退出 *********\n");printf("******************************************\n");
}int main()
{int op = -1;Contact con;ContactInit(&con);do {menu();printf("請選擇您的操作:\n");scanf("%d", &op);//要根據對應的op執行不同的操作switch (op){case 1:ContactAdd(&con);break;case 2:ContactDel(&con);break;case 3:ContactModify(&con);break;case 4:ContactFind(&con);break;case 5:ContactShow(&con);break;case 0:printf("退出通訊錄....\n");break;default:printf("輸入錯誤,請重新選擇您的操作!\n");break;}} while (op != 0);ContactDesTroy(&con);return 0;
}
Contact.h
#pragma once
#define NAME_MAX 20
#define GENDER_MAX 10
#define TEL_MAX 20
#define ADDR_MAX 100
//定義聯系人數據 結構
//姓名 性別 年齡 電話 地址
typedef struct personInfo
{char name[NAME_MAX];char gender[GENDER_MAX];int age;char tel[TEL_MAX];char addr[ADDR_MAX];
}peoInfo;//要用到順序表相關的方法,對通訊錄的操作實際就是對順序表進行操作
//給順序表改個名字,叫做通訊錄
typedef struct SeqList Contact; //sl
//通訊錄相關的方法//通訊錄的初始化
void ContactInit(Contact* con);
//通訊錄的銷毀
void ContactDesTroy(Contact* con);
//通訊錄添加數據
void ContactAdd(Contact* con);
//通訊錄刪除數據
void ContactDel(Contact* con);
//通訊錄的修改
void ContactModify(Contact* con);
//通訊錄查找
void ContactFind(Contact* con);
//展示通訊錄數據
void ContactShow(Contact* con);
Contact.c
#include"Contact.h"
#include"SeqList.h"//通訊錄的初始化
void ContactInit(Contact* con)//sl
{//實際上要進行的是順序表的初始化//順序表的初始化已經實現好了SLInit(con);
}
//通訊錄的銷毀
void ContactDesTroy(Contact* con)
{SLDestroy(con);
}
//通訊錄添加數據
void ContactAdd(Contact* con)
{//獲取用戶輸入的內容:姓名+性別+年齡+電話+地址peoInfo info;printf("請輸入要添加的聯系人姓名:\n");scanf("%s", info.name);printf("請輸入要添加的聯系人性別:\n");scanf("%s", info.gender);printf("請輸入要添加的聯系人年齡:\n");scanf("%d", &info.age);printf("請輸入要添加的聯系人電話:\n");scanf("%s", info.tel);printf("請輸入要添加的聯系人住址:\n");scanf("%s", info.addr);//往通訊錄中添加聯系人數據SLPushBack(con, info);
}int FindByName(Contact* con, char name[])
{for (int i = 0; i < con->size; i++){if (0 == strcmp(con->arr[i].name, name)){//找到了return i;}}//沒有找到return -1;
}//通訊錄刪除數據
void ContactDel(Contact* con)
{//要刪除的數據必須要存在,才能執行刪除操作//查找char name[NAME_MAX];printf("請輸入要刪除的聯系人姓名:\n");scanf("%s", name);int find = FindByName(con, name);if (find < 0){printf("要刪除的聯系人數據不存在!\n");return;}//要刪除的聯系人數據存在--->知道了要刪除的聯系人數據對應的下標SLErase(con, find);printf("刪除成功!\n");
}
//展示通訊錄數據
void ContactShow(Contact* con)
{//表頭:姓名 性別 年齡 電話 地址printf("%s %s %s %s %s\n", "姓名", "性別", "年齡", "電話", "地址");//遍歷通訊錄,按照格式打印每個聯系人數據for (int i = 0; i < con->size; i++){printf("%3s %3s %3d %3s %3s\n", //手動調整一下格式con->arr[i].name,con->arr[i].gender,con->arr[i].age,con->arr[i].tel,con->arr[i].addr);}
}
//通訊錄的修改
void ContactModify(Contact* con)
{//要修改的聯系人數據存在char name[NAME_MAX];printf("請輸入要修改的用戶姓名:\n");scanf("%s", name);int find = FindByName(con, name);if (find < 0){printf("要修改的聯系人數據不存在!\n");return;}//直接修改printf("請輸入新的姓名:\n");scanf("%s", con->arr[find].name);printf("請輸入新的性別:\n");scanf("%s", con->arr[find].gender);printf("請輸入新的年齡:\n");scanf("%d", &con->arr[find].age);printf("請輸入新的電話:\n");scanf("%s", con->arr[find].tel);printf("請輸入新的住址:\n");scanf("%s", con->arr[find].addr);printf("修改成功!\n");
}
//通訊錄查找
void ContactFind(Contact* con)
{//11char name[NAME_MAX];printf("請輸入要查找的聯系人姓名\n");scanf("%s", name);int find = FindByName(con, name);if (find < 0){printf("要查找的聯系人數據不存在!\n");return;}// 姓名 性別 年齡 電話 地址// 11 11 11 11 11printf("%s %s %s %s %s\n", "姓名", "性別", "年齡", "電話", "地址");printf("%3s %3s %3d %3s %3s\n", //手動調整一下格式con->arr[find].name,con->arr[find].gender,con->arr[find].age,con->arr[find].tel,con->arr[find].addr);
}