数据结构-链表的C语言使用

复习: 1.结构体类型的声明: struct Node { int data; int *pointer; }; 2.定义结构体指针变量 struct Node* p=(struct Node*)malloc(sizeof(struct Node)); 3.通过结构体指针变量访问 data 还有pointer p->data int p->pointer int * 4.指针变量之间的赋值 struct Node* q; q=p;// 把p存储的内容取出来 给q (p和q指向同一块空间) -------------------------------------------------------------------- 数据结构: 数据结构= 数据+ 结构 数据:能够输入到计算机，并且能够被它处理 结构:数据与数据之间的关系 逻辑结构： 1.集合 : 数据之间除了同属于一个集合之外，没有任何关系 2.线性结构: 1：1 3.树形结构: 1:n 4.图： n：m 物理结构: 1.顺序结构 数据与数据之间 存储的时候，地址空间的连续的 (数组) a[10] *(&a[0]+1) 2.链式结构 数据与数据之间 存储的时候，地址空间不连续的 （链表） 保存元素的值，还要保存下一个元素的地址 为什么要学数据结构: 程序=算法+数据结构 解决一个问题---》多种方法? 查询排名第 x 的学生信息。 1.排序 ---------》排序算法 一开始就把数据存储成有序的 2.直接到x 提高效率: 1.算法 ：多条指令序列集合 对多个算法进行评估 for(i=0;i<n;i++) { sum=sum+i ; } sum=(1+n)/2 执行效率: 1.事前分析： 语句的执行频度 （次数）T(n)=n T(n)=1 T（n）= n^2+3n+1 T(n)=3n+1 O(n) 渐进时间复杂度:O(n^2) for(i=0;i<10;i++) --->O(1) { sum=sum+i; } O(1)< O(log2N)<O(n)< O(nlog2N) <O(n2) <O(2^n)< O(n ^M) 2.事后分析：测试 2.数据的存储方式 ---------》 数据结构 线性结构： 特点: 1.存在唯一一个被称为 第一个 的数据元素 2.存在唯一一个被称为 最后一个 的数据元素 3.除第一个外，其他数据元素都具有唯一一个前驱 4.除最后一个外，其他数据元素都具有唯一一个后继 顺序结构：数组 int a[N+1];元素有N个 1.增加 在第x个位置增加一个数据元素m O(n) a[N]=a[N-1] a[N-1]=a[N-2] a[N-2]=a[N-3] .... a[x+1]=a[x]; a[x]=m 2.删除 在第x个位置删除一个数据元素 O(n) a[x]=a[x+1]; a[x+1]=a[x+2]; a[x+2]=a[x+3]; .... a[N-1] =a[N] 3.修改 在第x个位置把值改成y O(1) a[x]=y; 4.查询 查找第x个位置 O(1) a[x] 链式结构：链表 元素的类型: struct Node { int data;//存储的数据 数值域 struct Node*next;//下一个结点的地址 地址域 };--------》结点 1.链表 1.链表是由n个结点链接起来 2.线性表都有唯一的一个 第一个和最后一个，链表也要有第一个和最后一个 3.链表中的第一个结点的地址（头指针） 和 最后一个结点的地址（尾指针） struct Node *head=NULL;//头指针 struct Node *tail=NULL;//尾指针 创建链表： 1.创建头尾指针 2.增加结点，对结点进行赋初值 3.把结点链接起来 增加结点： 在m对应的结点前面，增加一个结点，增加结点的data 为x 找不到m，插入链表末尾。 删除结点: 找到元素x并且删除 修改结点: 查询: 写一个函数，查询链表中; 查找成功，返回结点的地址 查找失败，返回NULL 1.把创建链表和输出链表中的内容封装成函数。 creatList(); printList(); 作业： 1.已知(任意)有一个单链表，链表的结点有正有负， 请写出代码改变该单链表 ----->正数在前，负数在后 输入： 1 2 -4 3 -1 9 输出： 9 3 2 1 -4 -1（不要求输出一致，只需正在前 负数在后面即可） 2.删除结点代码补充完整