跳至主要內容

线性表

Cherzing2023年7月20日大约 6 分钟数据结构线性表

线性表

线性表的顺序表示和实现

  1. 初始化

    步骤：

    1. 为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址
    2. 将表的当前长度设为0

    代码：

    //初始化
const int MAXSIZE = 100;
bool InitList(SqList L)
{
    L.elem = new ElemType[MAXSIZE];
    if(!L.elem){
        return 0;
    }
    L.length = 0;
    return true;
}

  2. 取值

    步骤:

    1. 判断指定的位置序号i的值是否合理（1<=i<=L.length），若不合理，返回false
    2. 若值合理，则将第i个数据元素L.elem[i-1]赋值参数e，通过e返回第i个数据元素的传值
    //取值
int GetElem(SqList L,int i,ElemType e)
{
    if(i<1 || i>L.length){
        return -1;
    }
    e=L.elem[i-1];
    return e;
}

  3. 查找

    步骤：

    1. 从第一个元素起，依次将其值和e比较，若找到和e值相等的元素L.elem[i]，则查找成功，返回该元素的序号i+1
    2. 若查遍整个顺序表都没有找到，则查找失败，返回0
    //查找
int LocateElem(SqList L,ElemType e)
{
    for(int i=0;i<L.length;i++){
        if(e==L.elem[i]){
            return i+1;            
        }else{
            return 0;
        }
    }
    return 0;
}

  4. 插入

    1. 判断插入位置i是否合法(i值的合法范围为1<=i<=n+1)，若不合法返回FALSE
    2. 判断顺序表的存储空间是否已满，若满了，返回FALSE
    3. 将第n个至第i个元素依次向后移动一个位置，空出第i个位置(i=n+1时无序移动)
    4. 将要插入的元素e放入第i个元素
    5. 表长加一
    //插入
bool ListInsert(SqList &L,int i,ElemType e)
{
    if(i<1 || i>L.length+1)
    {
        return false;
    }
    if(L.length==MAXSIZE){//判断顺序表的存储空间是否已满
        return false;
    }
    for(int j=L.length-1;j>=i-1;j--){
        L.elem[j+1]=L.elem[j];    
    }
    L.elem[i-1] = e;
    ++L.length;
    return true;
}

  5. 删除

    步骤:

    1. 判断删除位置i是否合法(合法的值为1<=i<=n)，若不合法则返回FALSE
    2. 将第i+1个元素至第n个元素依次向前移动一个位置(i=n时无需移动)
    3. 表长减一
    //删除
bool ListDelete(SqList &L,int i)
{
    if(i>L.length && i<1){
        return false;
    }
    for(int j=i;j<=L.length-1;j++){
        L.elem[j-1]=L.elem[j];
    }
    --L.length;
    return true;
}

测试：

#include<iostream>
using namespace std;

typedef int ElemType;
typedef struct {
    ElemType *elem;
    int length;
} SqList;

//基本操作的实现

//初始化
const int MAXSIZE = 100;
bool InitList(SqList &L, int length) {
    L.elem = new ElemType[MAXSIZE];
    if (!L.elem) {
        return 0;
    }
    L.length = length;
    return true;
}

//赋值
int PushElem(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length) {
        return -1;
    }
    L.elem[i - 1] = e;
    return 0;
}

//取值
int GetElem(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) {
        return -1;
    }
    e = L.elem[i - 1];
    return e;
}

//查找
void LocateElem(SqList &L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (e == L.elem[i]) {
            cout<<"位置为"<<i + 1<<endl;
        }
    }
}

//插入
bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) {
        return false;
    }
    if (L.length == MAXSIZE) { //判断顺序表的存储空间是否已满
        return false;
    }
    for (int j = L.length - 1; j >= i - 1; j--) {
        L.elem[j + 1] = L.elem[j];
    }
    L.elem[i - 1] = e;
    ++L.length;
    return true;
}

//删除
bool ListDelete(SqList &L, int i) {
    if (i > L.length && i < 1) {
        return false;
    }
    for (int j = i; j <= L.length - 1; j++) {
        L.elem[j - 1] = L.elem[j];
    }
    --L.length;
    return true;
}

//打印
void PrintList(SqList &L) {
    for (int i = 0; i < L.length; i++) {
        cout << "第" << i + 1 << "个元素：" << L.elem[i] << endl;
    }
}

int main() {
    SqList L;
    InitList(L, 4);
    PushElem(L, 1, 1);
    PushElem(L, 2, 2);
    PushElem(L, 3, 3);
    PushElem(L, 4, 4);
    LocateElem(L, 4);
    PrintList(L);
    cout<<endl;

    //在第三个位置，插入元素5
    ListInsert(L, 3, 5);
    PrintList(L);
    cout<<endl;

    ListDelete(L, 1);
    PrintList(L);
    cout<<endl;

    return 0;
}

运行：

线性表的链式表示和实现

单链表

  1. 初始化

    1. 生成新节点作为头结点，用头指针L指向头结点
    2. 头结点的指针域置空
void Initlist(LinkList &L)
{
	L = new LNode;
	L->next = NULL;
}

  1. 取值

    1. 用指针p指向首元结点，用j做计数器初值赋为1
    2. 从首元结点开始依次顺着链域next向下访问，只要指向当前节点的指针p不为空(NULL)，并且没有到达序号为i的节点，则循环执行以下操作：
      • p指向下一节点
      • 计数器j加一
    3. 退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法(i大于表长n或i小于等于0)，取值失败返回ERROR；否则取值成功，此时j=i时，p所指的节点就是要找的第i个节点，用参数e保存当前节点的数据域，返回OK
    bool GetElem(LinkList &L, int i, int &e) {
	int j;
	LinkList p;
	p = L->next;
	j = 1;
	while (j < i && p) {
		p = p->next;
		j ++;
	}
	if (!p || j > i)
		return false;
	e = p -> data;
	return true;
}

  2. 查找

    1. 用指针p指向首元结点
    2. 从首元结点开始依次顺着链域next向下查找，只要指向当前节点的指针p不为空，并且p所指节点的数据域不等于给定值e，则循环执行以下操作：p指向下一节点
    3. 返回p。若查找成功，p此时指向节点的地址值；若查找失败，则p的值为NULL
    bool LocateElem(LinkList &L, int e) {
	LinkList p;
	p = L-> next;
	while (p && p->data != e)
		p = p->next;
	if (!p)
		return false;
	return true;
}

  3. 插入

    1. 查找节点ai-1并由指针p指向该节点
    2. 生成一个新节点*s
    3. 将新节点*s的数据域置为e
    4. 将新节点*s的指针域指向节点ai
    5. 将节点*p的指针域指向新节点*s
    bool ListInsert(LinkList &L, int i, int e) {
	int j;
	LinkList p, s;
	p = L;
	j = 0;
	while (p && j < i - 1) {
		p = p->next;
		j++;
	}
	if (!p || j > i - 1)
		return false ;
	s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

  4. 删除

    1. 查找节点ai-1并由指针p指向该节点
    2. 临时保存待删除的节点ai的地址在q中，以备释放
    3. 将节点*p的指针域指向ai的直接后继节点
    4. 释放节点ai的空间
    bool ListDelete(LinkList &L, int i) {
	LinkList p, q;
	int j = 0;
	p = L;
	while ((p->next) && (j < i - 1)) {
		p = p->next;
		j ++;
	}
	if (!(p->next) || (j > i - 1))
		return false;
	q = p->next;;
	p->next = q->next;
	delete q;
	return true;
}

  5. 创建单链表

    • 前插法

      void CreateList_H(LinkList &L)
{

    int n ;
	LinkList s; 
	L = new LNode;
	L ->next = NULL; 
	while(n--)
	{ 
	 	s = new LNode ; 
		cin>>s->data;
		s->next = L->next;
		L->next = s;
    }
}

    • 后插法

      void CreateList_R(LinkList &L)   //尾插法创建单链表 （尾插法是正序建表） 
{
   	//输入n个元素，建立到头结点的单链表
   	int n ;
   	LinkList  s, r;
   	L = new LNode;
	L->next = NULL;  //先建立一个带头结点的空链表 
	r = L;           //尾指针r指向头结点  （就他自己）
    cout<<"请输入元素个数 n: "<<endl;
	cin>>n;
	cout<<"请依次输入n个元素："<<endl;
	cout<<"前插法创建单链表..."<<endl;
	while(n--)
	{ 
	 	s = new LNode ;       //生成新结点s
		cin>>s->date;          //输入元素赋值给新结点的数据域
	    s->next = NULL;
	    r->next = s;           //将新结点插s插入尾结点*r之后
		r = s;                 //r指向新的尾结点s 
    }
}

循环链表

双向链表

顺序表和链表的比较

空间性能

时间性能

Cherzing
Copyright © 2024 Cherzing