数据结构——线性表

线性表：由同类型数据元素构成有序序列的线性结构

• 表中元素个数称为线性表的长度
• 没有元素时，称为空表
• 起始位置称表头，表结束位置称表尾

数组

存储

利用数组的连续空间顺序存放线性表的各元素

typedef struct LNode *List;
struct LNode{
	ElementType Data[MAXSIZE];
    int Last;
};
struct LNode L;
List PtrL;
//访问数据：L.Data[i]或PtrL->Data[i]
//线性表的长度：L.Last+1或PtrL->Last+1

主要操作

初始化

（建立空的顺序表）

List MakeEmpty(){
	List PtrL;
	PtrL = (List) new LNode;
    PtrL->Last=-1;
    return PtrL;
}

查找

int Find(ElementType X,LIst PtrL)
{
    int i=0;
    while(i<Ptrl->Last && PtrL->data[i]!=X)
        i++;
    if(i>PtrL->Last)  return -1;
    else return i;
}

插入

(第i(1<=i<=n+1)个位置上插入一个值为X新元素)

因为下标是从0开始，所以实际上需要把i-1及以后的所以元素都向后移动一位再在i-1位置放入新元素

void insert(ElementType X,int i,List PtrL)
{
    //判断表是否满和插入的位置是否合法
    if(PtrL->Last==MAXSIZE){
        cout<<"表满";
        return;
    }
    if(i<1 || i > PtrL->Last+2){
        cout<<"位置不合法";
        return;
    }
    //移动i-1及以后的元素
    for(int j=PtrL->Last;j>=i-1;j--){
        PtrL->Data[j+1]=PtrL->Data[j];
    }
    PtrL->Data[i-1]=X;//插入数据
    PtrL->Last++;//Last仍指向最后一个位置
}

删除

（删除第i（1<=i<=n）位置的元素）

void Delete (int i,List PtrL){
    //判断i是否合法
    if(i<1 || i > PtrL->Last+1){
        cout<<"不存在第"<<i<<"个元素";
        return;
    }
    //把i-1位置后面的元素向前挪
    for(int j=i;j<PtrL->Last;j++){
        PtrL->Data[j-1]=PtrL->Data[j];
    }
    PtrL->Last--;//Last仍指向最后
}

链式表

基本原理

我们需要先创建一个结构体（里面包含一个数据、一个后继指针）

data 用来储存数据，

next 后继指针用来储存下一节点的地址。

struct node{
   int data;
    node* next;
};

我们再创建几个结构体指针 node *head， *p， *q， *t。

head指针：用来储存链表的首地址。

p指针：为临时指针，来储存新建的节点

q指针：储存上一节点的地址

t指针：用来遍历节点

#include <iostream>
using namespace std;


struct node
{
	int data;
	node* next;
};
int main()
{
	

	node* p, * q, * t, * head;
	head = NULL;			//初始化头指针为空
	q = NULL;
	int n, a;
	cout << "输入数据个数";
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		p = (node*)new node;	//申请一个空间,用来存放一个节点，并临时指针p指向该节点
		p->data = a;			//储存数据在data里
		p->next = NULL;			//设置当前节点的后继指针指向空，即为链尾
		if (head == NULL) head = p; 	//如果头指针为空，则头指针指向p
		else q-> next=p ;				//如果不是第一个节点，则把上一节点的后继指针指向临时指针
		q = p;
	}
	t = head;
	while (t != NULL) {
		cout << t->data << "\t";
		t = t->next;
	}
	return 0;
}

主要操作

求表长

进行一次遍历

int Length(node* PtrL)
{
    node8 p=PtrL; //p指向头指针
    int j=0;
    while(p!=0){
        p=p->next;
        j++;
    }
    return j;
}

查找

（1）按序号查找

输入第k位置，返回k位置的地址

node* FindKth(int k,node* head)
{
    node* p=head;
    int i=1;
    for(p!=NULL && i<k)
    {
        p=p->next;
        i++;
    }
    if(i==k) return p;//找到第k个，返回指针
    else return NULL;//没找到
}

(2)按值查找

node *Find(ElementType X,node* head)
{
    node* p=head;
    while(p!=NULL && p->Data!=x)
        p=p->next;
    if(p->Data==x) return p;//找到
    else return NULL;//没找到
}

插入

插入数据就是让前一个数据的后继指针指向新的节点，新的节点的后继指针指向后一个节点。

//插入在第i-1（1<=i<=n+1)个节点后插入一个值为X的新节点

node *INsert(ElementType X,int i,node* head)
{
    node* p,* s;
    if(i==1){   	//插入点在表头
        s=(node*)new node;
        s->next=head;
        s->Data=X;
        return s; //返回新表头指针
    }
    p = FindKth(i-1,head);//查找第i-1节点
    if(p = NULL){
        cout << "参数错误";
        return NULL;
    }
    else{
        s=(node*)new node;//申请新节点
        s->next=p->next;//临时指针后继指针指向现在节点的下一个节点
        s->data=X;
        p->next=s;//当前节点的后继指针指向临时节点
        return head;//返回头指针
    }
}

删除

(1)找到i-1节点，p指向

(2)指针s指向要被删除的结点，p的下一结点

(3)修改指针，删除s所指向结点

(4)最后释放s所指结点的空间

node* Delete(int i,node* head)
{
    node* p,* s;
    if(i==1){
        s=head;
        if(head != NULL)
            head = head->next;
        else return NULL;
        delete s;
        return head;
    }
    p = FinKth(i-1,head);
    if(p==NULL){
        cout << "第" <<i-1 <<"结点不存在";
    }else if(p->next==NULL)
        cout<< "第" << i <<"结点不存在";
    else {
        s=p->next;
        p->next=s->next;
        delete s;
        return head;
    }
}

全部代码：

#include <iostream>
using namespace std;
//定义结构体
struct node
{
	int Data;
	node* next;
};
//查找函数
node* FindKth(int k, node* head) {
	node* p = head;
	int i = 1;
	while (p != NULL && i < k) {
		p = p->next;
		i++;
	}
	if (i == k) return p;
	else return NULL;
}

//删除
node* Delete(int i, node* head)
{
	node* p, *s;
	if (i == 1) {
		s = head;
		if (head != NULL) head = head->next;
		else return NULL;
		delete s;
		return head;
	}
	p=FindKth(i - 1, head);
	if (p == NULL) {
		cout << "第" << i - 1 << "个元素不存在";
		return NULL;
	}
	else if (p->next == NULL) {
		cout << "第" << i << "个元素不存在";
		return NULL;
	}
	else {
		s = p->next;
		p->next = s->next;
		delete s;
		return head;
	}

}
//插入
node* Insert(int X,int i, node* head)
{
	node* p,* q;
	if (i == 1) {
		p = (node*)new node;
		p->Data = X;
		p->next = head;
		return p;
	}
	q = FindKth(i - 1, head);
	if (q == NULL) {
		cout << "参数错误";
		return NULL;
	}
	else {
		p = (node*)new node;
		p->Data = X;
		p->next = q->next;
		q->next = p;
		return head;
	}
}
int main() {
	node* head, * p, * q, * t;
	head = NULL;
	q = NULL;
	int n, a;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		p = (node*)new node;
		p->Data = a;
		p->next = NULL;
		if (head == NULL) {
			head = p;
		}
		else {
			q->next = p;
		}
		q = p;
	}
	Insert(100, 3, head);
	t = head;
	Delete(2, head);
	while (t != NULL) {
		cout << t->Data << " ";
		t = t->next;
	}

}

多重链表

多重链表：链表中的结点可能同时属于多个链

多重链表中节点的指针域会有多个（但包含两个指针域的链表并不一定是多重链表，比如双向链表）

to be continue …