1.表是可以是线性结构
| 学号 | 姓名 |
|---|---|
| 19(数据项) | jams(数据项) |
| 20(数据项) | ming(数据项) |
19 jams或 20 ming是数据元表单个的是数据项‘’线性结构可以表示为 19 jams->20 ming
2.什么是逻辑结构?:具有相同类型的有限序列(元素排序的位置,排兵布阵+操作的方法)
a1 a2 a3 .... an (空表长度为0)
3.什么是存储结构? 主要包括 线性存储结构(数组)+链式存储结构,后面的图结果用到了邻接表(其实就是数组+链表结构,可以结合使用)
4.线性表(逻辑结构+存储结构[线性结构])的特点
1.元素个数有限性2.类型相同,例如 ((jams,18),(ming,19))3.元素类型的抽象性(如2)4.相邻元素序偶关系 a1无前驱,an无后继,中间元素只有一个前驱和后继如: a1(无前驱)--->a2(只有一个前驱后继)--->....--->an(无后继)
- 线表的抽象数据类型(ADT) 来表达他的逻辑结构
DataModel: 相同数据类型,前驱后继关系Operation:InitList: 初始化表DestroyList: 销毁表Length: 得到线性表长度Get: 得到下标对应的值Locate: 根据值得到下标Insert:在第i个位置插入一个新元素xDelete:删除第i个元素Empty: 判断表为空endADT
6.线表的存储结构
1.用一段连续的地址存储2.依次存表的数据元素
7.为什么数组下标必须从0开始
比如 int [3]; //如果下标从0开始,他会计算第一个的地址为 //系统分配的地址+0(下标)*size(int) 如果int是4字节的话//就是 系统分配的地址+0//下标为1时 系统分配的地址+4
8.线性表的完整c语言代码
#include<stdio.h>
#include<stdlib.h>
/*将顺序表的存储结构定义和各个函数定义放到这里*/
#define MaxSize 100 /*假设顺序表最多存放100个元素*/
typedef int DataType; /*定义线性表的数据类型，假设为int型*/
typedef struct {DataType data[MaxSize]; /*存放数据元素的数组*/int length; /*线性表的长度*/
} SeqList;
void InitList(SeqList *L) { //就是把长度设置为0L->length = 0;
}
int CreatList(SeqList *L, DataType a[ ], int n) {int i;if (n > MaxSize) {printf("顺序表的空间不够，无法建立顺序表\n");return 0;}for(i = 0; i < n; i++)L->data[i] = a[i];L->length = n;return 1;
}
int Empty(SeqList *L) {if (L->length == 0) return 1; /*顺序表为空返回1*/else return 0;
}
int Length(SeqList *L) {return L->length;
}
void PrintList(SeqList *L) {int i;for(i = 0; i < L->length; i++)printf("%d ", L->data[i]); /*输出线性表的元素值，假设为int型*/printf("\n");
}
int Locate(SeqList *L, DataType x) {int i;for (i = 0; i < L->length; i++)if (L->data[i] == x) return i+1; /*返回序号*/return 0; /*退出循环，说明查找失败*/
}
int Get(SeqList *L, int i, DataType *ptr) {if (i < 1 || i > L->length) {printf("查找位置非法，查找失败\n");return 0;} else {*ptr = L->data[i - 1];return 1;}
}
int Insert(SeqList *L, int i, DataType x) {int j;if (L->length >= MaxSize) {printf("上溢错误，插入失败\n");return 0;}if (i < 1 || i > L->length + 1) {printf("位置错误，插入失败\n");return 0;}for (j = L->length; j >= i; j--) //全部元素向后移动 /*j表示元素序号*/L->data[j] = L->data[j - 1];L->data[i - 1] = x;L->length++;return 1;
}
int Delete(SeqList *L, int i, DataType *ptr) {int j;if (L->length == 0) {printf("下溢错误，删除失败\n");return 0;}if (i < 1 || i > L->length) {printf("位置错误，删除失败\n");return 0;}*ptr = L->data[i - 1]; /*取出位置i的元素*/for (j = i; j < L->length; j++) //从i这个下标开始向前覆盖 /* j表示元素所在数组下标*/L->data[j - 1] = L->data[j];L->length--;return 1;
}
int main( ) {int r[8] = {12,32,43,55,34,76,81,59}, i, x;SeqList L; /*定义变量L为顺序表类型*/CreatList(&L, r, 8); /*建立具有5个元素的顺序表*/printf("当前线性表的数据为：");PrintList(&L); /*输出当前线性表1 2 3 4 5*/Insert(&L, 2, 8); /*在第2个位置插入值为8的元素*/printf("执行插入操作后数据为：");PrintList(&L); /*输出插入后的线性表1 8 2 3 4 5*/printf("当前线性表的长度为：%d\n", Length(&L)); /*输出线性表的长度6*/printf("请输入查找的元素值：");scanf("%d", &x);i = Locate(&L, x);if (0 == i) printf("查找失败\n");else printf("元素%d的位置为：%d\n", x, i);printf("请输入查找第几个元素值：", &i);scanf("%d", &i);if (Get(&L, i, &x) == 1) printf("第%d个元素值是%d\n", i, x);else printf("线性表中没有第%d个元素\n", i);printf("请输入要删除第几个元素：");scanf("%d", &i);if (Delete(&L, i, &x) == 1) { /*删除第i个元素*/printf("删除第%d个元素是%d，删除后数据为：", i, x);PrintList(&L); /*输出删除后的线性表*/} else printf("删除操作失败\n");return 0;
}9.线性表(包括顺序表和单链表),我们说说他的链式存储结构的特点
1.逻辑与物理次序不一定相同(不像数组 例如 下标0到1 地址是连续的)2.用指针表示 标记更新
10.关于单链表的一些术语(说出来,可以让我们听起来就比较专业)
1.C语言的 单链表的(Node)结构体 data(数据域) next(指针域)
: 指向最后节点的指针头节点:第一个节点的指针 ,方便边界处理(方便写代码)尾节点:最后一个节点的指针 ,next指向null的
11.链表的完整c语言代码
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
/*将单链表的结点结构定义和各个函数定义放到这里*/
typedef int DataType; /*定义线性表的数据类型，假设为int型*/
typedef struct Node { /*定义单链表的结点类型*/DataType data;struct Node *next;
} Node;
Node *InitList( ) //主要创建一个节点然后next设置为NULL,返回头节点
{Node *first = (Node *)malloc(sizeof(Node)); /*生成头结点*/first->next = NULL; /*头结点的指针域置空*/return first;
}
int Empty(Node *first) //判断单链表是否为空,只需要判断first的next为NULL就为空
{if (first->next == NULL) return 1; /*单链表为空，返回1*/else return 0;
}
//遍历单链表并输出,复制一个头指针的next给p指针,p不为NULL(可以一个一个遍历) 继续遍历
//事实上,我们也可以直接 p赋值first指针 判断p->next!=null也可以,但是这里使用的可以与(我们使用的逻辑相对应)
//我先移动到我要使用的位置,然后一一next 比较简单
//我到next一个元素,一个一一next 理解比较困难
void PrintList(Node *first)
{Node *p = first->next; /*工作指针p初始化*/while (p != NULL) {printf("%d ", p->data); /*输出结点的数据域，假设为int型*/p = p->next; /*工作指针p后移，注意不能写作p++*/}printf("\n");
}
int Length(Node *first) //求长度和遍历一样 直接返回遍历次数
{Node *p = first->next; /*工作指针p初始化*/int count = 0; /*累加器count初始化*/while (p !=NULL) {p = p->next;count++;}return count;
}//得到x元素的位置, 以后我要养成查询在前,修改在后的习惯//链表没有下标所以,没有返回0的,逻辑还是遍历(好的代码可以重复利用来写!!!)
int Locate(Node *first, DataType x)
{Node *p = first->next; /*工作指针p初始化*/int count = 1; /*累加器count初始化*/while (p != NULL) {if (p->data == x) return count; /*查找成功，结束函数并返回序号*/p = p->next;count++;}return 0; /*退出循环表明查找失败*/
}
//得到指定位置的值
//只需要判断count的大小，这里使用while不是使用for因为while不能确定循环次数,而for需要
//还要判断是否到结尾了没有元素
int Get(Node *first, int i, DataType *ptr)
{Node *p = first->next; /*工作指针p初始化*/int count = 1; /*累加器count初始化*/while (p != NULL && count < i) {p = p->next; /*工作指针p后移*/count++;}if (p == NULL) {printf("位置错误，查找失败\n");return 0;} else {*ptr = p->data;return 1;}
}
int Insert(Node *first, int i, DataType x)
{Node *s = NULL, *p = first ; /*工作指针p初始化为指向头结点*/int count = 0;while (p != NULL && count < i - 1) { /*查找第i-1个结点*/p = p->next; /*工作指针p后移*/count++;}if (p == NULL) {printf("位置错误，插入失败\n");return 0;} else {s = (Node *)malloc(sizeof(Node));s->data = x; /*申请一个结点s，数据域为x*///必须先修改new出来的节点的next,改前一个节点的next,以免数据丢失s->next = p->next; p->next = s; /*将结点s插入到结点p之后*/return 1;}
}
Node *CreatList(DataType a[ ], int n)
{ //先创建头节点,然后头插法一一连接int i;Node *s = NULL;Node *first = (Node *)malloc(sizeof(Node));first->next = NULL; /*初始化头结点*/for (i = 0; i < n; i++) {s = (Node *)malloc(sizeof(Node));s->data = a[i]; /*为每个数组元素建立一个结点*/s->next = first->next;first->next = s; /*将结点s插入到头结点之后*/}return first;
}int Delete(Node *first, int i, DataType *ptr)
{Node *p = first, *q = NULL; /*工作指针p要指向头结点*/int count = 0;DataType x;while (p != NULL && count < i - 1) { /*查找第i-1个结点*/p = p->next;count++;}if (p == NULL || p->next == NULL) { /* p结点或p的后继结点不存在*/printf("位置错误，删除失败\n ");return 0;} else {q = p->next;*ptr = q->data; /*存储被删结点和被删元素值*/p->next = q->next; /*摘链*/free(q);return 1;}
}
void DestroyList(Node *first)
{Node *p = first;while (first != NULL) { /*依次释放每一个结点，包括头结点*/first = first->next;free(p);p = first;}
}
int main( )
{int r[5] = {1, 2, 3, 4, 5}, i, x;Node *first = NULL;first = CreatList(r, 5);printf("当前线性表的数据为：");PrintList(first); /*输出当前链表1 2 3 4 5*/Insert(first, 2, 8); /*在第2个位置插入值为8的结点*/printf("执行插入操作后数据为：");PrintList(first); /*输出插入后链表1 8 2 3 4 5*/printf("当前单链表的长度为：%d\n", Length(first)); /*输出单链表长度6*/printf("请输入查找的元素值：");scanf("%d", &x);i = Locate(first, x);if (i != 0) printf("元素%d的元素位置为：%d\n", x, i);else printf("单链表中没有元素%d\n", x);printf("请输入要删除第几个元素：");scanf("%d", &i);if (Delete(first, i, &x) == 1) { /*删除第i个元素*/printf("删除的元素值是%d，执行删除操作后数据为：", x);PrintList(first); /*输出删除后链表*/} else printf("删除操作失败\n");DestroyList(first); /*释放单链表*/return 0;
}12.总结出写代码方法论(由上面的Get方法思考得出)
13. (给个值)插入元素操作也可以分为 头插法(上面的代码就是)和尾插法(在尾节点后面插入元素)
14.循环单链表(单链表的尾节点的next指向first头节点) 多个rear尾指针判断j结束
15.循环双链表(有pre前指针和next指针)
16.顺序表和链表的比较
1.存储分配方式顺: 静态存储分配,连续单元空间,逻辑用下标表示链: 动态分配(存储地址不一定连续),链接使用指针2.空间顺: 有限空间,存储密度100%(不存储其他东西,比如指针,额外因为结构导致的数据)只 存元素链:存储密度不高,动态分配空间,空间弹性你自己分配,3.时间复杂度1.按位查 顺: O(1) 随机存取(拿到什么下标就拿到什么元素)链: O(n) 顺序存取(只能一个一个遍历 计数来查找)2.按值操作链,顺: O(n)都遍历一遍3.插入删除顺: O(n) 插入必须插入元素后移, 删除需要前移覆盖之前的元素链: O(1) 指针理论上速度可以达到O(1)直接操作内存地址4.总结1.长度知道: 顺不知道:链2.操作 少插入和删除(查找)用 顺常用插入删除 用 链
