线性表
#线性表#的存储结构包括：
顺序表
链表
链表的五种形式：
- 单链表
- 带头节点：head->next ==NULL
- 不带头节点：head == NULL
—
- 双链表
- 带头节点：head->next ==NULL
- 不带头节点：head == NULL
—
- 循环单链表
- 带头节点：head == head->next
- 不带头节点：head == NULL
—
- 循环双链表
- 带头节点：检查head->prior和head->next两者中的任意一个是否等于head即可
- 不带头节点：head == NULL
—
-
静态链表：借助一维数组来表示
静态链表
顺序表和链表的区别
- 基于空间：
- 顺序表的存储空间是一次性分配，链表的存储空间是动态分配的；
- 顺序表的存储密度=1，而链表的存储密度<1。
——
- 基于时间：
- 顺序表能随机存取，而链表只能顺序存取；
- 顺序表插入删除时几乎需要移动一半的元素::时间复杂度为O(n)::，而链表不需要移动元素，只需要修改指针即可。
定义顺序表
int A[maxSize];
int n;
//或者这样写
typedef struct Sqlist
{
int data[maxSize];
int length;
}Sqlist;
定义链表
- 单链表
typedef struct LNode
{
int data;
struct LNode* next;
}LNode;
- 双链表
typedef struct DLNode
{
struct DLNode* prior;
int data;
struct DLNode* next;
}DLNode;
初始化顺序表时只需要将长度设置为0便可
习题
- 顺序表用数组[m+n]A表示，前m个元素递增有序，后n个元素递增有序，设计一个算法，使得整个顺序表有序。
void insertElem（int A[],int m,int n）
{
int temp;
int i,j;
for(i = m ; i < m+n ; i++)
{
temp = A[i];
for(j = i-1 ; j >= 0 && temp < A[j] ; j—)
A[j+1] = A[j];//此时j位置有个坑，指针在j位置
//此刻指针跳到j-1位置
//此刻，j元素<=temp，j+1元素> temp
A[j+1] = temp;
}
}
::时间复杂度为O(mn)::
::空间复杂度为O(1)，算法所需的额外存储空间与数据规模无关！::
- 两个递增有序的单链表A、B，元素个数分别为m和n，都有头结点。求A-B,结果放在A链表里面。
void difference (LNode* A,LNode* B)
{
LNode * p = A->next;
LNode * q = B->next;
LNode * prior = A;
while(p != NULL && q !=NULL)
{
if(p->data < q->data)
{
prior = p;
p = p->next;//只移动p及其前缀
}
else if(p->data > q->data)
{
q = q->next;//只移动q
}
else
{
pre->next = p->next;
free(p);
p = pre->next;
}
}
}
::时间复杂度为O(m+n)::
- 为什么在单循环链表中设置尾指针比设置头指针更好？
::因为可以用它来方便的查找链表的开始结点和终端结点,查找时间均为O(1)::
- 有一个顺序表L，全是整型数据，设计一个算法，将L中所有小于表头元素的整数放在前半部分，大于表头元素的帧数放在后半部分。
void move (Sqlist& L){
int temp;
int i = 0;
int j = L.length-1;
temp = L.data[i];
while(i<j){
while(i<j && L.data[j]>temp)
j—;
if(i<j){
L.data[i] = L.data[j];
i++;
}
while(i<j && L.data[i]<=temp)//加一个等号，结果大不一样！
i++;
if(i<j){
L.data[j] = L.data[i];
j—;
}
}
L.data[i] = temp;
}
- 有一个递增非空链表，设计一个算法删除值重复的结点。
void deletelist(LNode* L){
LNode *p = L->next;
LNode *q = p->next;
LNode *r;
while(q != NULL){ //q从头到尾遍历一遍链表，找不同
while(q != NULL && q->data == p->data) q = q->next;
if(q != NULL){
p = p->next;
p->data = q->data;
}
}
q = p->next;
p->next = NULL; //将有用部分和重复部分斩断联系
while(q != NULL){ //删除重复的部分
r = q;
q = q->next;
free(r);
}
}
- 设计一个算法删除单链表L（有头结点）中的一个最小值结点。
void deletemin(LNode *L){
LNode *pre = L, *p = L->next, *min = p, *minpre = pre;
while(p != NULL){
if(p->data < min->data){
min = p;
minpre = pre;
}
p = p->next;
pre = pre->next;
}
minpre->next = min->next;
free(min);
}
::遍历链表需要两指针，删除一结点需要两指针，一共需要4指针::
反之，如果要删除最大的结点呢？::也得要4个指针。::
- 设计一个算法来逆置一个带头结点的单链表。
void reverse(LNode *L){
//利用头插法，可以使链表逆序
LNode *p = L->next;
LNode *q;
L->next = NULL;
while(p != NULL){
q = p->next;
p->next = L->next;
L->next = p;
p = q;
}
}
- 设计一个算法，逆序打印单链表数据。
void reprint(LNode *L){
if(L != NULL){
reprint(L->next);
cout<<L->data<<“ “;
}
cout<<endl;
}
- 设计一个算法，输出带头结点的单链表的倒数第k个结点的值。
void kvalue(LNode *L, int k){
LNode *p = L->next;
LNode *q = L;
int i = 1;
while(p != NULL){
p = p->next;
i++;
if(i > k)
q = q->next;
}
if(q = L)
cout<<0;
else
cout<<q->data;
}
