自学内容网 自学内容网

C语言强化-2.线性表&代码

与408的关联:1. 顺序表结合排序出了很多大题。2. 链表本身出很多大题!

顺序表的顺序表示原理

  1. 线性表的特点:
    1. 表中元素的个数是有限
    2. 表中元素的数据类型都相同。意味着每一个元素都占用相同大小的空间。
    3. 表中元素具有逻辑上的顺序性,在序列中各元素排序有其先后顺序。
  2. 线性表第一个元素的数组下标是0

线性表的顺序表示(顺序表)

顺序表的定义

#define MaxSize 50  //定义线性表的长度
typedef struct{    
ElemType data[MaxSize];  //顺序表的元素
int len;    //顺序表的当前长度
}SqList;    顺序表的类型定义

优点:

  1. 可以随机存取(根据表头元素地址和元素序号)表中任意一个元素。
  2. 存储密度高,每个结点只存储数据元素。

缺点:

  1. 插入和删除操作需要移动大量元素。
  2. 线性表变化较大时,难以确定存储空间的容量。
  3. 存储分配需要一整段连续的存储空间,不够灵活。 

插入操作

  • 最好情况:新元素插入到表尾,不需要移动元素,最好时间复杂度 = O(1)
  • 最坏情况:新元素插入到表头,需要将原有的n个元素全都向后移动,最坏时间复杂度 = O(n)
  • 平均情况:假设新元素插入到任何一个位置的概率相同,平均移动元素的次数是n/2,时间复杂度 = O(n)
//判断插入位置i是都合法(满足i <= length + 1)
//判断存储空间是否已满(即插入e后是否会超出数组长度)
for(int j = L.length;j >= i;j--)  //将第i个元素及之后的元素后移
L.data[j] = L.data[j - 1];
L.data[i =-1] = e;  //在位置i处放入e
L.length++;  //长度加1

删除操作

  • 最好情况:删除表尾元素,不需要移动元素,最好时间复杂度 = O(1)
  • 最坏情况:删除表头元素,需要将后续的n - 1个元素全都向前移动,最坏时间复杂度 = O(n)
  • 平均情况:假设删除任何一个元素的概率相同,平均移动元素的次数为(n-1)/2,时间复杂度 = O(n)
e = L.data[i - 1];  //将被删除的元素赋值给e
for(int j = i;j < L.length;j++)  //将第i个元素后哦的元素前移
L.data[j - 1] = L.data[j];  //注意位序、数组下标的关系,并从前面的元素依次移动
L.length--;  //长度减1

动态分配

#define InitSize 10  //顺序表的初始长度
typedef struct{
ElemType * data;  //指示动态分配数组的指针
int MaxSize;  //顺序表的最大容量
int length;  //顺序表的当前长度
}SeqList;  //顺序表的类型定义(动态分配方式)
//C的初始动态分配语句
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
//C++的初始动态分配语句
L.data = new ElemType[InitSize];

顺序表的初始化及插入操作实践

#include <stdio.h>

#define MaxSize 50
typedef int ElemType;//让顺序表存储其他类型元素时可以快速完成代码修改
typedef struct {
    ElemType data[MaxSize];
    int length;
}SqList;
//顺序表的插入,因为L会改变,因此这里要用引用
bool ListInsert(SqList &L,int i,ElemType element){
    //判断i(插入的位置)是否合法
    if(i < 1 || i > L.length + 1){
        return false;
    }//如果存储空间满了,不能插入
    if(L.length == MaxSize){
        return false;//未插入返回false
    }
    //把后面的元素依次往后移,空出位置,放入插入的元素
    for(int j = L.length;j >= i;j--){
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = element;//放入要插入的元素
    L.length++;//顺序表长度要+1
    return true;//插入成功返回true
}

//打印顺序表
void PrintList(SqList L){
    int i;
    for(i = 0;i < L.length;i++){
        printf("%3d",L.data[i]);
    }
    printf("\n");
}

//顺序表的初始化及插入
int main() {
    SqList L;//顺序表的名称
    bool ret;//ret用来装函数的返回值
    L.data[0]=1;
    L.data[1]=2;
    L.data[2]=3;
    L.length = 3;
    ret = ListInsert(L,2,60);
    if(ret){
        printf("insert sqlist success\n");
        PrintList(L);
    }else{
        printf("insert sqlist failed\n");
    }
    return 0;
}
//输出
insert sqlist success
  1 60  2  3

顺序表的删除及查询实践

//删除顺序表中的元素,i是要删除的元素的位置,e是为了获取被删除的元素的值
bool ListDelete(SqList &L,int i,ElemType &e){
    //判断删除的元素的位置是否合法
    if(i < 1 || i > L.length){
        return false;
    }
    e = L.data[i -1];//首先保存要删除元素的值
    int j;
    for(j = i - 1;j < L.length-1;j++){//往前移动元素
        L.data[j] = L.data[j + 1];
    }
    L.length--;//顺序表长度-1
    return true;
}
//查找某个元素的位置,找到就返回对应的位置,没找到就返回0
int LocateElem(SqList L,ElemType element){
    int i;
    for(i = 0;i < L.length;i++){
        if(element == L.data[i]){
            return i+1;//因为i是数组的下标,i+1以后才是顺序表的下标
        }
    }
    return 0;//循环结束没找到
}
int main() {
    SqList L;//顺序表的名称
    bool ret;//ret用来装函数的返回值
    L.data[0]=1;
    L.data[1]=2;
    L.data[2]=3;
    L.length = 3;
    ElemType del;//删除的元素存入del中
    ret = ListDelete(L,1,del);
    if(ret){
        printf("delete sqlist success\n");
        printf("delete element = %d\n",del);
        PrintList(L);
    }else{
        printf("delete sqlist failed\n");
    }
    printf("-----------------\n");
    int pos;//存储元素位置
    pos = LocateElem(L,60);
    if(pos){
        printf("find this element\n");
        printf(" element pos = %d\n",pos);
    }else{
        printf("don't fint this element\n");
    }
    return 0;
}
//输出
delete sqlist success
delete element = 1
 60  2  3
-----------------
find this element
 element pos = 1

线性表的链式存储

线性表的链式表示(链表)

单链表

typedef struct LNode{  //定义单链表结点类型
ElemType data;  //每个结点存放一个数据元素
struct LNode *next;  //指针指向下一个结点
}LNode, *LinkList;

若链表有头结点,则头指针永远指向头结点,不论链表是否为空,头指针均不为空。头指针是链表的必需元素,它标识一个链表。

  1. 头指针:链表中第一个结点的存储位置,用来标识单链表。
  2. 头结点:在单链表第一个结点之前附加一个结点,为了操作上方便。

//初始化一个单链表(带头结点)
bool InitList(LinkList &L){
L = (LNode *) malloc(sizeif(LNode));  //分配一个头节点
if (L == NULL)  //内存不足,分配失败
return false;
L -> next = NULL;  //头节点之后暂时还没有结点
return true;
}

优点:

  1. 插入和删除操作不需要移动元素,只需要修改指针。
  2. 不需要大量的连续存储空间。

缺点:

  1. 单链表附加指针域,也存在浪费存储空间的缺点。
  2. 查找操作时需要从表头开始遍历,依次查找,不能随机存取。

插入
//创建新结点
q = (LNode*)malloc(sizeof(LNode))
q -> data = x;
//表头/中间插入元素
q -> next = p -> next;
p -> next = q;
//表尾插入元素
p -> next = q;
q -> next = NULL;
删除
//表头、中间、表尾删除操作
p = GetElem(L,i - 1);//查找删除位置的前驱结点
q = p -> next;
p -> next = q -> next;
free(q);
查找
//按序号查找节点值
LNode *p = L -> next;
int j = 1;
while(p && j < i){
p = p -> next;
j++;
}
return p;
//按值查找节点
LNode *p = L -> next;
while(p != NULL && p -> data != e){
p = p -> next;
}
return p;

原文地址:https://blog.csdn.net/Annabelle___/article/details/140557199

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!