线性表(插入/清除数据/快慢指针查找中间数据)

╰半夏微凉° 2022-06-17 06:08 271阅读 0赞

**1.概念**

**线性表 ：**顺序存储结构线性表 及 链式存储结构线性表

**链式存储结构线性表（线性链表）：**

具有链接存储结构的线性表，它用一组地址任意的存储单元存放线性表中的数据元素，逻辑上相邻的元素在物理上不要求也相邻，不能随机存取。一般用结点描述：结点（表示数据元素） =数据域（数据元素的映象） + 指针域（指示后继元素存储位置）

**顺序存储结构线性表：**

顺序存储结构就是用一组地址连续的存储单元依次存储该线性表中的各个元素。由于表中各个元素具有相同的属性，所以占用的存储空间相同

**优缺点：**

顺序存储需要开辟一个定长的空间，读写速度快，缺点不可扩充容量(如果要扩充需要开辟一个新的足够大的空间把原来的数据重写进去)

链式存储无需担心容量问题，读写速度相对慢些，由于要存储下一个数据的地址所以需要的存储空间比顺序存储大。

**2.代码**

//定义一个链式存储结构的线性表 尾插法操作 及 清除单链表数据 
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    #define ElemType int    //宏定义
    #define OK    1
    #define ERROR 0
    #define TRUE  1
    #define FALSE 1
    
    typedef int Status;     //定义类型的别名
    
    typedef struct Node     //定义一个结构体 作为线性表中的节点
    {
    	ElemType data;      //数据域
    	struct Node* Next;  //指针域
    } Node;                 //结构体别名
    typedef struct Node* LinkList;  //实例化一个节点对象，名为LinkList
     
    /*定义尾插法创建链表*/
    void CreateListTail(LinkList *L, int n)
    {
    	LinkList p, r;
    	int i;
    	srand(time(0));
    	*L = (LinkList)malloc(sizeof(Node)); 
    	//向系统申请分配指定size个字节的内存空间,返回指向被分配内存的指针
    	r = *L;
    	for (i = 0; i < n; i++)
    	{
    		p = (Node *)malloc(sizeof(Node)); //为临时节点分配内存
    		p->data = rand() % 100 + 1;  //获取随机数作为节点内容
    		r->Next = p;
    		r = p;
    	}
    	r->Next = NULL;
    }
    
    /*清除单链表数据*/
    Status ClearList(LinkList *L)
    {
    	LinkList p, q;
    	p = (*L)->Next;
    	while(p)
    	{
    		q = p->Next;
    		free(p);
    		p = q;
    	}
    	(*L)->Next = NULL;
    	return OK;
    }

//使用快慢指针 快速查找单链表的中间元素 Status GetMidNode(LinkList L, ElemType *e) { LinkList search, mid; mid = search = L; //search指针移动速度是mid指针的两倍 while (search->Next != NULL) { if (search->Next->Next != NULL) { search = search->Next->Next; mid = mid->Next; } else { search = search->Next; } } *e = mid->data; return OK; }