目录
- 🚀前言
- 🦜任务目标
- 🌟顺序表实现
- 🐍链表实现
🚀前言
大家好！我是 EnigmaCoder。
本文介绍线性表的实验，使用顺序表和链表实现通讯录管理，包含初始化、插入、删除、查询、输出。
🦜任务目标
-
线性表数据结构应用：利用顺序表和链表实现动态存储通讯录信息，包括初始化、插入、删除、查询和遍历功能。
-
核心算法实现：
-
动态扩容机制（
realloc实现顺序表空间扩展）； -
按学号/姓名的精准查询（基于自定义比较函数）；
-
元素的插入与删除（涉及数据移位操作）。
- 学生数据样例：
| 学号（num） | 姓名（name） | 性别（sex） | 电话号码（tel） | QQ号码（qq） | 备注 |
|---|---|---|---|---|---|
| 1001 | 张三 | 男 | 13812345678 | 1234567890 | 常规数据（男） |
| 1002 | 李四 | 女 | 13987654321 | 9876543210 | 常规数据（女） |
| 1003 | 王芳 | 女 | 15800001111 | 456789123 | QQ号为9位（合法） |
| 1010 | 刘畅 | 男 | 18666668888 | 123456789012 | QQ号为12位（最大值） |
🌟顺序表实现
#include<stdio.h>
#include<stdlib.h>
#include<string.h>#define LIST_INIT_SIZE 10
#define LISTIHCREAHENT 5typedef struct {int num;char name[20];char sex[3];char tel[14];char qq[12];
}ElemType;typedef struct {ElemType* elem;int length;int listsize;
}SqList;int InitList_Sq(SqList& L) {L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if (!L.elem)exit(-1);L.length = 0;L.listsize = LIST_INIT_SIZE;
}int ListInsert_Sq(SqList& L, int i, ElemType e) {ElemType* newbase;if (i<1 || i>L.length + 1) {return 0;}if (L.length == L.listsize) {newbase = (ElemType*)realloc(L.elem, (LIST_INIT_SIZE + LISTIHCREAHENT) * sizeof(ElemType));if (!L.elem)exit(-1);L.elem = newbase;L.listsize += LISTIHCREAHENT;}for (int j = L.length - 1; j >= i - 1; j--) {L.elem[j + 1] = L.elem[j];}L.elem[i - 1] = e;L.length++;return 1;
}int ListDelete_Sq(SqList& L, int i, ElemType& e) {if (i<0 || i>L.length)return 0;for (int j = i ; j <= L.length-1; j++) {L.elem[j-1] = L.elem[j];}L.length--;return 1;
}int LocateElem_Sq(SqList L, ElemType e, int(*equal)(ElemType, ElemType)) {int i = 1;while (i <= L.length && !equal(e, L.elem[i - 1])) i++;if (i <= L.length) return 1;else return 0;}int comparebynum(ElemType x, ElemType y) {return x.num == y.num ? 1 : 0;
}int comparebyname(ElemType x, ElemType y) {if (strcmp(x.name, y.name) == 0)return 1;else return 0;
}void inputOne(ElemType& x) {scanf("%d%s%s%s%s", &x.num, x.name, x.sex, x.tel, x.qq);
}void outputOne(ElemType x) {printf("%d\t%s\t%s\t%s\t%s\n", x.num, x.name, x.sex, x.tel, x.qq);
}void Output(SqList L) {for (int i = 0; i <= L.length-1; i++) {outputOne(L.elem[i]);}
}int main() {SqList L;int choice,i,y,m;ElemType e,t,x;do{printf(" 通讯录管理系统\n");printf("====================================\n");printf(" 0:退出\n");printf(" 1:建立通讯录\n");printf(" 2:插入\n");printf(" 3:删除\n");printf(" 4:查询\n");printf(" 5:输出\n");printf("====================================\n");printf("请选择0-5\n");scanf("%d",&choice);switch(choice){case 0: exit(1);case 1: InitList_Sq(L);break;case 2: printf("input i:");scanf("%d",&i);printf("input one record:");inputOne(e);ListInsert_Sq(L,i,e);break;case 3: printf("input i:");scanf("%d",&i);ListDelete_Sq(L,i,t);break;case 4: printf("41.姓名查询\n42.学号查询\n");printf("输入选项: ");scanf("%d",&y);if(y!=41&&y!=42) {printf("请重新选择。\n");break; }if(y==41){printf("需查询的姓名：");scanf("%s",t.name);m=LocateElem_Sq(L,t,comparebyname); }else {printf("需查询的学号：");scanf("%d",&t.num);m=LocateElem_Sq(L,t,comparebynum);} if(m) outputOne(L.elem[m-1]);else printf("查询失败。\n");break;case 5: Output(L);break; }}while(choice);free(L.elem);return 0;
}
🐍链表实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct {int num;char name[20];char sex[3];char tel[14];char qq[12];
} ElemType;typedef struct LNode {ElemType data;struct LNode* next;
} LNode, * LinkList;void InitList_L(LinkList& L) {L = (LinkList)malloc(sizeof(LNode));L->next = NULL;
}int ListInsert_L(LinkList& L, int i, ElemType e) {LinkList p = L, s;int j = 0;while (p && j < i - 1) {p = p->next;j++;}if (!p || j > i - 1) return -1;s = (LinkList)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return 1;
}int ListDelete_L(LinkList& L, int i, ElemType& e) {LinkList p = L, q;int j = 0;while (p->next && j < i - 1) {p = p->next;j++;}if (!(p->next) || j > i - 1) return -1;q = p->next;p->next = q->next;e = q->data;free(q);return 1;
}LinkList LocateElem_L(LinkList L, ElemType e, int(*op)(ElemType a, ElemType b)) {LinkList p = L->next;while (p && !op(p->data, e)) {p = p->next;}return p;
}int comparebynum(ElemType x, ElemType y) {return x.num == y.num ? 1 : 0;
}int comparebyname(ElemType x, ElemType y) {return strcmp(x.name, y.name) == 0 ? 1 : 0;
}void inputOne(ElemType& x) {printf("请输入学号、姓名、性别、电话、QQ：");scanf("%d%s%s%s%s", &x.num, x.name, x.sex, x.tel, x.qq);
}void outputOne(ElemType x) {printf("%d\t%s\t%s\t%s\t%s\n", x.num, x.name, x.sex, x.tel, x.qq);
}void outputList(LinkList L) {LinkList p = L->next;while (p) {outputOne(p->data);p = p->next;}
}int main() {LinkList L;int choice, i, y;ElemType e, t;do {printf(" 通讯录管理系统\n");printf("====================================\n");printf(" 0:退出\n");printf(" 1:建立通讯录\n");printf(" 2:插入\n");printf(" 3:删除\n");printf(" 4:查询\n");printf(" 5:输出\n");printf("====================================\n");printf("请选择0 - 5\n");scanf("%d", &choice);switch (choice) {case 0:exit(1);case 1:InitList_L(L);break;case 2:printf("input i:");scanf("%d", &i);inputOne(e);if (ListInsert_L(L, i, e) == -1) {printf("插入失败\n");}break;case 3:printf("input i:");scanf("%d", &i);if (ListDelete_L(L, i, e) == -1) {printf("删除失败\n");}else {printf("删除的记录为：");outputOne(e);}break;case 4:printf("41.姓名查询\n42.学号查询\n");printf("输入选项: ");scanf("%d", &y);if (y != 41 && y != 42) {printf("请重新选择。\n");break;}if (y == 41) {printf("需查询的姓名：");scanf("%s", t.name);LinkList result = LocateElem_L(L, t, comparebyname);if (result) {outputOne(result->data);}else {printf("查询失败。\n");}}else {printf("需查询的学号：");scanf("%d", &t.num);LinkList result = LocateElem_L(L, t, comparebynum);if (result) {outputOne(result->data);}else {printf("查询失败。\n");}}break;case 5:outputList(L);break;}} while (choice);LinkList p = L;while (p) {LinkList temp = p;p = p->next;free(temp);}return 0;
}
