复（预）习老师的ppt的屑。
顺序线性表部分：?
计算地址：
loc(ai) =loc(a1)+(i-1)×k?
?顺序表的基础要点：
1 无需为表示元素间的逻辑关系而增加额外的存储空间，存储密度大（100%）；2 可随机存取表中的任一元素; 3 插入或删除一个元素时，需平均移动表的一半元素，具体的个数与该元素的位置有关，在等概率情况下，插入n/2，删除(n-1)/2；O(n) ；4 存储分配只能预先进行分配; 5 将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是：n。
1：两个线性表LA和LB分别表示两个集合A和B，现求一个新的集合A=A∪B。
void union( List &La, List Lb)
{因为要修改A，传入的是A的指针
La_len = ListLength(La);计算出两个长度
Lb_len = ListLength(Lb);
for( i=1; i<=Lb_len; i++){
GetElem(Lb, i, e);得到B的第i位置的元素
if(!LocateElem(La, e, equal))如果不在A内
ListInsert(La, ++La_len, e);加在A的后面，并且A的长度加一
}
}
时间复杂度为O(len(a) * len(b))。
2： 两个线性表LA和LB中的数据元素按值非递减有序排列，现将LA和LB归并为一个新的线性表，LC中的数据元素仍按值非递减有序排列。LA = (3, 5, 8, 11)? LB = (2, 6, 8, 9, 11, 15, 20) LC = (2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20) ??
void MergeList( List La, List Lb, List &Lc)修改哪个哪个传指针
{ InitList(Lc);创建
La_len = ListLength(La); Lb_len = ListLength(Lb);
i=j=1; k=0;
while( (i<=La_len) && (j<=Lb_len)){
a小是a，b小是b。
GetElem(La, i, a); GetElem(Lb, j, b);
if(a<=b) { ListInsert(Lc, ++k, a); ++i; }
else { ListInsert(Lc, ++k, b); ++j; }
}
while(i<=La_len){
GetElem(La, i++, a); ListInsert(Lc, ++k, a);}
while(j<=Lb_len){
GetElem(Lb, j++, b); ListInsert(Lc, ++k, b);}
}
?时间复杂度: O(ListLength(La)+ListLength(Lb))?。
3：顺序表的基本操作
初始化 Status InitList_Sq ( SqList &L)
{
L.elem = (ElemType * )malloc(LIST_INIT_SIZE*
sizeof(ElemType));
if(!L.elem)
exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
L.elem = new ElemType[LIST_INIT_SIZE];
插入 Status ListInsert_Sq (SqList &L, int i, ElemType e)
{
if( (i<1) || (i>L.length+1) )
return ERROR;
if(L.length >= L.listsize){
realloc(…); ….; // 越界处理 ；
}
q = &(L.elem[i-1]);
for( p = &(L.elem[L.length-1]; p>=q; --p)
*(p+1) = *p;
*q = e;
++L.length;
return OK;
}
插入时间复杂度分析：
?则长度为 n 的线性表中插入一个元素所需移动元素次数的期望值为: ? E?= ∑ pi (n – i + 1），如果等概率插入pi=1/(n+1)，E=n/2，O(n)。?
删除 Status ListDelete_Sq (SqList &L, int i, ElemType &e)
{
if( (i<1) || (i>L.length) )
return ERROR;
p = &(L.elem[i-1]);
e = *p;
q = L.elem+L.length-1;
for( ++p; p<=q; ++p)
*(p-1) = *p;
--L.length;
return OK;
}
?删除元素时间复杂度：
E=∑ qi (n – i)，当等概率qi=1/n的时候，E=(n-1)/2，O(n)。
链式表部分：
用一组任意的存储单元存储线性表的元素，不要求逻辑上相邻的元素在物理位置上也相邻；
??
数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。?
※基本概念
1结点：数据元素的存储映象。
2头指针：?指示链表中第一个结点的存储位置，单链表可由头指针唯一确定。设置头结点的目的是统一空表与非空表的操作，简化链表操作的实现。
3首元结点：链表中存储线性表中第一个数据元素的结点。
?基本操作：
初始化线性表InitList(L)
该运算建立一个空的单链表,即创建一个头结点。
void InitList(LinkList &L)
{
L=(LinkList)malloc(sizeof(LNode));
/*创建头结点*/
L->next=NULL;
}
销毁线性表DestroyList(L)
释放单链表L占用的内存空间。即逐一释放全部结点的空间。
void DestroyList(LinkList L)
{ LinkList p=L, q=p->next;
while (q!=NULL)
{ free(p);
p=q;q=p->next;
}
free(p);
}
插入
Status ListInsert(LinkList &L, int i, ElemType e)
{
p = L; j = 0;
while (p && j < i-1) { p = p->next; ++j }
if (!p || j>i-1) return ERROR;
s = (LinkList) malloc( sizeof (LNode) );
s->data = e;
s->next = p->next; ①
p->next = s; ②
return OK;
}
删除
Status ListDelete(LinkList &L, int i, ElemType &e)
{
p = L; j = 0;
while (p->next && j < i-1) { p = p->next; ++j }
if (!(p->next) || j>i-1) return ERROR;
r = p->next;
e = r->data;
p->next = p->next->next; //(p->next = r->next;) ①
free(r);
return OK;
}
删除*p结点的语句序列
q = L;
while( q->next != p) q = q->next;
q->next = p->next;
free(p);
删除首元结点的语句序列
q = L->next;
L->next = q->next;
free(q);
删除最后一个结点的语句序列
while(p->next->next != NULL) p = p->next;
q = p->next;
p->next = NULL;
free(q);头插法建表
CreateList_H(LinkList &L, int n)
{
L = (LinkList) malloc( sizeof (LNode) );
L->next = NULL;
for( i=n; i>0; --i){
s = (LinkList) malloc( sizeof (LNode) );
scanf( &s->data);
s->next = L->next; ①
L->next = s; ②
}
}
尾插法建表
就是引入了一个tail始终指向链表的末尾，使得插入变的简单。
CreateList_T(LinkList &L, int n)
{
tail = L = (LinkList) malloc( sizeof (LNode) );
L->next = NULL;
for( i=n; i>0; --i){
s = (LinkList) malloc( sizeof (LNode) );
scanf( &s->data);
s->next = NULL;
tail->next = s;
tail = s;
}
}
变式：
1 循环链表：
循环链表是另一种形式的链式存储结构，?可从当前结点出发，访问到任一结点。有循环单链表、?多重循环链表。
操作与线性单链表基本一致，差别只是在于算法中的循环结束条件不是p是否为空，而是p是否等于头指针。
2? 双向链表：
?typedef struct DuLNode{ ? ?
?????????ElemType ? ? ? ? ? ? ? data; ? ? ?
????????struct DuLNode ? ?*prior; ? ? ?struct DuLNode ? ?*next;
}DuLNode, ?*DuLinkList;
?3 双向循环链表
静态链表：
有些高级程序设计语言并没有指针类型，如FORTRAN和JAVA。我们可以用数组来表示和实现一个链表，称为静态链表。 可定义如下：
#define ?MAXSIZE ?1000 ? //最多元素个数
typedef ?struct{ ? ? ? ?
????????ElemType data; ? ? ? ?int ? ? ? ? ? ? ?cur; //游标，指示器
}component, SLinkList[MAXSIZE];
练习题：
约瑟夫环
习题集P79。编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出圈为止。
问题输入 ：输入数据第一行为两个正整数n和m，分别表示人的个数及初始随机数，每组数据的第二行为n个整数，表示每个人持有的密码。
问题输出 ：用一行输出n个整数表示依次出圈人的编号，整数之间用空格分隔 ??
方法一：尾插法建立链表，循环判断。终止条件是循环链表只有一个元素?
#include<stdio.h>
#include<stdlib.h>
typedef struct link
{
int data;
int id;
struct link* next;
}List;
List* Creatlist() {
List* L = (List*)malloc(sizeof(List));
L->next = NULL;
return L;
}
void Insert(List* p, int d,int i)
{//插入新的节点并且返回尾节点
//printf("INSERT>>>\n");
List* L = (List*)malloc(sizeof(List));
L->next = NULL;
L->data = d; L->id = i;
p->next = L;
return ;
}
int main()
{ //初始化过程
int num, m,i,d; scanf_s("%d%d", &num, &m);
//创建n个节点，写循环指针
struct link* head =Creatlist();
scanf("%d", &d);
head->data = d; head->id=1;
List* p = head; List* Q = (List*)malloc(sizeof(List));
for (i = 2; i <= num; i++)
{
//printf("INSERT>>");
scanf("%d", &d);
Insert(p,d,i);
p = p->next;
}
if (num == 1)
{
printf("1 ");
return 0;
}
p->next = head;//循环
//执行判断
while (1)
{
for (i = 1; i < m; i++)
{
p = head;
head = head->next;
}
m = head->data;
printf("%d ", head->id);
p->next = head->next;
Q = head; head = head->next;
free(Q);
if (head->next == head->next->next)
break;
}
printf("%d", head->id);
free(head);
return 0;
}方法二：整体上优化了。?使用两个for循环控制循环次数，没有引入乱七八糟的函数。
#include<stdio.h>
#include<stdlib.h>
typedef struct list{
int data;
int id;
struct list *next;
}L;
//注意有两个数据，一个是编号，一个是分配的数值
int main()
{
int n,m;
scanf("%d%d",&n,&m);
//1 建表
L*list=(L*)malloc(sizeof(L));
L*tail=list,*head=list,*p=list;
head->id=1;head->next=NULL;
//第一个需要单独
scanf("%d",&head->data);
for(int i=2;i<=n;i++)
{
L*node=(L*)malloc(sizeof(L));
node->next=NULL;
node->id=i;
scanf("%d",&node->data);
tail->next=node;
tail=node;
}
tail->next=head;
if(m==1)
{
printf("1");
return 1;
}
//2 循环判断
for(int i=1;i<=n;i++)
{
for(int j=1;j<m;j++)//锁定前一个
{//同时使得p和head都 循环
p=head;//上一个
head=head->next;//当前
}
m=head->data;
printf("%d ",head->id);
p->next=head->next;
tail=head;
head=head->next;
free(tail);
}
return 1;
} ?
