lil_DengZi's Notes

线性表

8分钟阅读

ADT

Note

ADT 线性表(list)
Data

算法遵循线性结构，只有一个前驱元素，一个后续元素（除头尾），数据之间为一对一关系

Operation

  • InitList(*L):初始化列表，L为列表名
  • ListEmpty(L):判断线性表是否为空表若空返回ture,非空返回false
  • ClearList(*L):线性表清空
  • GetElem(L,i,*e):线性表L中第i个位置元素值返回给e
  • LocateElem(L,e): 线性表L查与给定值e相等的元素，查找成功，返回元素在表中配对的序号，返回0失败
  • ListInsert(*L,i,e):L中i位置插入新元素e
  • ListDelete(*L,i,*e):删除L中i位置元素,返回其值至e
  • ListLength(L):返回线性表长度
  • UnionL(List *La,list Lb):结合线性表AB
  • …

endADT

线性表的顺序表示

即物理存储结构中元素相邻，地址连续

线性表顺序存储结构的优缺点

  • 在存，读数据时，不管是哪个位置，时间复杂度都是O(1),插入删除时，时间复杂度O(n).
  • 说明线性表适合元素个数稳定，不经常插入、删除元素，更多是存取数据的应用。

线性表链式存储结构

  • 在头部插入时，时间复杂度O(1),中间或尾部插入删除时，时间复杂度为O(n),读取数据也是O(n).
  • 主要在利用零碎的内存空间,以及无法预测数据量时使用.

具体实现

表体

  • 线性表
typedef struct Node
 
{
    elem data;
    int length;
}Node;
 
Node* head = NULL;
  • 单向链表
typedef struct Node
 
{
    elem data;
    Node* next;
}Node;
 
Node* head = NULL;
  • 双向链表
typedef struct Node
 
{
    elem data;
    Node* next;
    Node* prev;
}Node;
 
Node* head = NULL;
Node* tail = NULL;
  • 循环链表
typedef struct Node
 
{
    elem data;
    Node* next;
}Node;
 
Node* head = NULL;
//List *L = NULL;

初始化链表

  1. 线性表
void InitList(Node** head)
{
    Data *data = (Data*)malloc(sizeof(Data[1024]));
    head->elem = data;
}
 
Node *List;
InitList(&List);
  1. 单双链表
void InitList(Node** head)
{
    *head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    //head->prev = NULL;
}
 
Node *List;
InitList(&List);
  1. 循环链表
void InitList(Node** head)
{
    *head = (Node*)malloc(sizeof(Node));
    (*head)->next = *head;
    //head->prev = NULL;
}
 
Node *List;
InitList(&List);
title:循环链表注意事项
collapse:open 
 
1. 初始化中(\*head)->next = NULL改成(\*head)->next = \*head;
 
2. 循环结束条件改成p->next = head;

判断是否为空

bool ListEmpty(Node** head)
{
    if(head)//循环链表:head->next = NULL;
    {
        return true;
    }
    return false;
}

清空链表

void ClearList(Node* p)
{
    if(p->next == NULL)
    {
        free(p);
        p = NULL;
        return;
    }
    ClearList(p->next);
}

查找元素

查找元素位置

插入节点

  • 头部插入

方法一

Node* insertNode(Node* t_head, int x)
 
{
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = x;
    /*
    if(t_head == NULL)
    {
        t_head = temp;
        return;
    }
    temp->prev = temp;
    */
    temp->next = t_head;
    t_head = temp;
    /*
    temp->next = t_head;
    t_head = temp;
    可以替换为
    temp->next = NULL;
    if(t_head != NULL)temp->next = t_head;
    t_head = temp;
    */
    return t_head;
}
 
insertNode(head, data);

方法二

void insertNode(Node** p_t_head, int x)
 
{
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = x;
    temp->next = *p_t_head;
    *p_t_head = temp;
}
 
insertNode(&head, data);
  • 任意位置插入
Node* insertNode(Node* t_head, int d, int n)
{
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = d;
    temp->next = NULL;
    if(n == 1)
    {
        temp->next = t_head;
        t_head = temp;
        return t_head;
    }
    Node* temp2 = t_head;
    for(int i = 0; i < n - 2; i++)
    {
        temp2 = temp2->next;
    }
    temp->next = temp2->next;
    temp2->next = temp;
    
    return t_head;
}
 
insertNode(head, data, position);

删除节点

  • 删除指定位置的节点
Node* Delete(Node* t_head, int n)
{
    Node* temp = t_head;
    if(n == 1)
    {
        t_head = temp->next;
        free(temp);
        temp = NULL;
        return t_head;
    }
    int i;
    for(int i = 0; i < n - 2; i++)
    {
        temp = temp->next;
    }
    Node* temp2 = temp->next;
    temp->next = temp2->next;
    free(temp2);
    temp2 = NULL;
    return t_head;
}
 
Delete(head, position);

链表长度

int ListLength(Node** head)
{
    Node* p = *head;
    int count = 1;
    while(p)
    {
        count++;
        p = p->next;
    }
    return count;
}

特殊操作

反转链表

  • 反转链接
void Reverse(Node** t_head)
{
    Node *curr, *prev, *next;
    curr = *t_head;
    prev = NULL;
    while(curr != NULL)
    {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    *t_head = prev;
}
 
Reverse(&head);
  • 反转打印(递归)
void Print(Node* p)
{
    if(p != NULL)
    {
        Print(p ->next);//上下句调换位置即可正向反向打印
        printf("%d ", p->data);
    }
    return;
}
 
/*
    if(p == NULL)
    {
        return;
    }
    printf("%d ", p->data);//上下句调换位置即可切换正向反向打印
    Print(p ->next);
    
*/
  • 反转链接(递归)
void Reverse(Node* p)
{
    if(p->next == NULL)
    {
        head = p;
        return;
    }
    Reverse(p->next);
    Node* q = p->next;
    q->next = p;
    /*
    Node* q = p->next;
    q->next = p;
    可改成
    p->next->next = p;
    */
    p->next = NULL;
}

多项式表达

LinkList plus(LinkList L1, LinkList L2, LinkList LP)
{ // 多项式相加
	LinkList p1, p2, LPP;
	LPP = LP;
	p1 = L1->next;
	p2 = L2->next;
	while (p1 != NULL && p2 != NULL)
	{
		if (p1->ei == p2->ei)
		{ // 当两个项指数相等时存入新链表中
			LinkList sum = (LinkList)malloc(sizeof(Node));
			sum->ei = p1->ei;
			sum->ci = p1->ci + p2->ci;
			LP->next = sum;
			LPP->ei++;
			LP = sum;
			p1 = p1->next;
			p2 = p2->next;
		}
		else if (p1->ei > p2->ei)
		{ // 当第一个链表的项指数大于第二个链表的项指数时
			LP->next = p2;
			LPP->ei++;
			LP = p2;
			p2 = p2->next;
		}
		else if (p1->ei < p2->ei)
		{ // 反之
			LP->next = p1;
			LPP->ei++;
			LP = p1;
			p1 = p1->next;
		}
	}
	if (p1 == NULL && p2 == NULL)
		return LPP;
	else if (p1 != NULL && p2 == NULL)
	{
		LP->next = p1;
		int cnt = 0;
		while (p1 != NULL)
		{
			p1 = p1->next;
			cnt++;
		}
		LPP->ei += cnt;
		return LPP;
	}
	else if (p1 == NULL && p2 != NULL)
	{
		LP->next = p2;
		int cnt = 0;
		while (p2 != NULL)
		{
			p2 = p2->next;
			cnt++;
		}
		LPP->ei += cnt;
		return LPP;
	}
}
	
	
	
LinkList cut(LinkList L1, LinkList L2, LinkList LC)
{ // 多项式相减(多项式1减去多项式2)
	LinkList p1, p2, LCC;
	LCC = LC;
	p1 = L1->next;
	p2 = L2->next;
	while (p1 != NULL && p2 != NULL)
	{
		if (p1->ei == p2->ei)
		{ // 当两个项指数相等时存入新链表中
			LinkList cut = (LinkList)malloc(sizeof(Node));
			cut->ei = p1->ei;
			cut->ci = p1->ci - p2->ci;
			LC->next = cut;
			LCC->ei++;
			LC = cut;
			p1 = p1->next;
			p2 = p2->next;
		}
		else if (p1->ei > p2->ei)
		{ // 当第一个链表的项指数大于第二个链表的项指数时
			LinkList lowp = (LinkList)malloc(sizeof(Node));
			lowp->ei = p2->ei;
			lowp->ci = -(p2->ci);
			LC->next = lowp;
			LCC->ei++;
			LC = lowp;
			p2 = p2->next;
		}
		else if (p1->ei < p2->ei)
		{ // 反之
			LinkList lowp = (LinkList)malloc(sizeof(Node));
			lowp->ei = p1->ei;
			lowp->ci = -(p1->ci);
			LC->next = lowp;
			LCC->ei++;
			LC = lowp;
			p1 = p1->next;
		}
	}
	
	if (p1 == NULL && p2 == NULL)
		return LCC;
	else if (p1 != NULL && p2 == NULL)
	{
		LC->next = p1;
		int cnt = 0;
		while (p1 != NULL)
		{
			p1 = p1->next;
			cnt++;
		}
		LCC->ei += cnt;
		return LCC;
	}
	else if (p1 == NULL && p2 != NULL)
	{
		while (p2 != NULL)
		{
			LinkList temp = (LinkList)malloc(sizeof(Node));
			temp->ei = p2->ei;
			temp->ci = -(p2->ci);
			LC->next = temp;
			LCC->ei++;
			LC = temp;
			p2 = p2->next;
		}
		LC->next = NULL;
		return LCC;
	}
 
}

关系图谱

最近的笔记

反向链接