线性表

目录

0.PTA得分截图

1.本周学习总结

1.1总结线性表内容

一：顺序表和有序表的操作

a）顺序表结构体的定义

typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};
  • 使用typedef来给结构体指针起一个新名字，便于后续操作，并且这里多了一个position变量，用来保存线性表中最后一个元素的位置

b)顺序表插入

bool Insert( List L, ElementType X, Position P ){
     Position i;
     if(L->Last==MAXSIZE-1){
     	printf("FULL");
        return false;
	 }
	if(P<0||P>L->Last+1){
		printf("ILLEGAL POSITION");
		return false;
	}
	for(i=L->Last;i>=P;i--)
		L->Data[i+1]=L->Data[i];
		L->Data[P]=X;
		L->Last++;
		return true; 
}
  • 顺序表的插入过程，是对数组元素移动的过程

c）顺序表的删除

法一：
void DelNode(SqList& L, int min, int max)
{
	int i = 0;
	while (i < L->length)
	{
		if (L->data[i] >= min && L->data[i] <= max)
		{
			for (int j = i; j < L->length-1; j++)
			{
				L->data[j] = L->data[j + 1];
				
			}
			L->length--; i--;
		}
		i++;
	}

}
  • 这里要注意如果是对多个元素进行删除的话，删除一个元素后需要把i的值减一，然后i的值再加一，不然会跳过删除元素的后一个元素
法二：
void DelNode(SqList& L, int min, int max)
{
      inti,j;
      i=j=0;
      
      while(i<L->length)
      {
          if(L->data[i]>=min&&L->data[i]<=max)
          {
               i++;
          }
          L->data[j]=L->data[i];
          j++;
          i++;
      }
}

d）删除重复数据

void DelSameNode(List& L, int a[], int n)
{
	L = new SqList;
	L->length = n;
	int i = 0;
	for (i=0; i < maxsize; i++)
	{
		L->data[i] = 0;
	}
	i = 0;
	while (i < n)
	{

		if (L->data[a[i]] == 0)
		{
			L->data[a[i]] = 1;
		}
		else
		{
			L->length--;
		}
		i++;
	}
}
  • 这里先对结构体中的数组进行赋值，全部赋为0，然后让a[]里的元素成为结构体中数组的下标，找到一个数后，就对data数组的值置1；

e）对有序表的操作，是对数组的元素多了排序

一：冒泡排序法
	for (q = 1; q <= k; q++)
	{
		
		for (j = 0 ; j < n-q; j++)
		{
			
			if (a[j] > a[j+1])
			{
				term = a[j];
				a[j] = a[j+1];
				a[j+1] = term;
			}	
		}
	}
二：选择排序法
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = i; j < n; j++)
		{
			if (L->data[i] > L->data[j])
			{
				temp = L->data[i];
				L->data[i] = L->data[j];
				L->data[j] = temp;
			}
	}

二：链表的操作

a）链表的结构体定义

typedef struct LNode  		//定义单链表结点类型
{
	ElemType data;
	struct LNode *next;		//指向后继结点
} LNode,*LinkList;
  • 使用typedef来给结构体和结构体指针起一个新名字，便于后续操作

b）头插法

void CreateListF(LinkList& L, int n)//头插法建链表，L表示带头结点链表，n表示数据元素个数
{
	 L = new struct LNode;//用new申请空间
	L->next = NULL;  //让头结点的next指向空
	LinkList ptr =L;
	int i = 0;
	int num;
	

	while (i < n)
	{
		cin >> num;
		LinkList p = new struct LNode;
		p->data = num;
		p->next = ptr->next;
		ptr->next = p;
		i++;		
	}


}

  • while循环中操作步骤：

  • 1.用new申请空间，并给p->data赋值

  • 2.让p节点的next指向头结点ptr的next

  • 3.再让头结点ptr的next指向p

  • 这个过程中，ptr的位置一直不变，变得是ptr的next，每增加一个新节点，ptr的next就会指向这个新节点，而这个新节点的next则指向原来头节点next指向的位置。

c）尾插法

void CreateListR(LinkList &L, int n)//尾插法建链表，L表示带头结点链表，n表示数据元素个数
{
	 L = new struct LNode;
	LinkList ptr =L;
	L->next=NULL;    //让头节点的next指向空
	int i = 0;
	int num;
	while (i < n)
	{
		cin >> num;
		LinkList p = new struct LNode;
		p->data = num;
        p->next=NULL;
        ptr->next=p;
        ptr=p;	
		i++;		
	}
}

  • while循环中的操作步骤

  • 1.new一个新节点，并赋值

  • 2.由于是尾插法，所以申请的p节点一直都是链表的最后一个节点，所以让p->next=NULL;ptr这个尾指针一开始指向头结点，然后让ptr->next指向新申请的尾节点，再让ptr指向这个p

d）链表插入

void ListInsert(LinkList& L, ElemType e)//有序链表插入元素e
{
	LinkList p, ptr;
	p = L;
	ptr = L->next;

	while (p)
	{
		if (ptr&&ptr->data < e)
		{
			ptr = ptr->next;
			p = p->next;
		}
		else
		{
			LinkList q = new struct LNode;
			q->data = e;
			q->next = ptr;
			p->next = q;
			break;
		}
	}
}

  • while循环中的操作步骤

  • 1.先找到对应的位置，ptr指向p的后继节点

  • 2.然后在ptr和p之间插入一个刚new出来的节点q，先让q->next指向ptr，然后让p->next指向q

e)链表删除

1）删除某一个节点
void ListDelete(LinkList& L, ElemType e)//链表删除元素e
{
    	if (L->next == NULL)
	{
		return;
	}

	LinkList p, ptr, temp;
	p = L;
	ptr = L->next;
	while (ptr)
	{
		if (ptr->data == e)
		{
			temp = ptr;
			p->next = ptr->next;
			delete temp;
			return;
		}
		p = p->next;
		ptr = ptr->next;
	}

	if (ptr == NULL)//链表为空
	{
		cout << e << "找不到！" << endl;
	}
}

  • while循环中的操作步骤

  • 1.先找到要删除的节点位置，让临时指针temp和ptr指向这个节点，p是ptr的前驱节点

  • 2.让p->next=ptr->next,再delete temp;

2）删除全部节点
void DestroyList(LinkList &L) 
{
	LinkList p = L;
 	while (L) 
	 {
	  	p = L;
	   	L = L->next;
		delete p;
	 }
}

f）链表逆置

法一：

void ReverseList(LinkList& L)
{
    LNode *p,*pre;

    pre=L->next;//保留后面的节点
    L->next=NULL;
    
    while(pre)  //对链进行遍历
    {
        p=pre;
        pre=pre->next;   //相当于头插法
        p->next=L->next;
        L->next=;//头结点的位置不变
    }
}

法二：

List Reverse( List L )
{
    Position Old_head, New_head, Temp;
    New_head = NULL;
    Old_head = L->Next;

    while ( Old_head ) 
    {
        Temp = Old_head->Next;
        Old_head->Next= New_head;  
        New_head = Old_head;  
        Old_head = Temp; 
    }
    
         L=New_head;
         return L;
}

三：双链表

a）双链表结构体的定义

typedef struct DNode  //声名双链表节点的类型
{
   ElemType data;
   struct DNode *prior;  //指向前驱节点
   struct DNode *next;
}linkList,*DlinkList;//指向后继节点
  • 双链表的特点
  • 1.从任一节点出发可以快速找到其前驱节点和后继节点；
  • 2.从任一节点出发可以访问其它节点
  • 双链表和单链表的区别，其实无论是从构建，删除，插入等操作，对next指针域的操作是不变的，多的是对前驱节点的操作

b）头插法

void creat_list(DlinkList &head,int n)
{
    Dlinklist p;
    int i;
    head=new linkList;  //创建头结点
    head->next=head->prior=NULL;
    for(i=1;i<n;i++)
    {
         p=new linkList;
         p->data=i;
         p->next=head->next;  //新节点插入到头结点之后，首节点之前
         if(head->next)//如果不是头结点，则让头结点的下一个节点的前驱节点的指向p
         head->next->prior=p;
         head->next=p;
         p->prior=head;
    }
}

c）尾插法

void creat_list(DlinkList &head,int n)
{
    Dlinklist p;
    int i;
    head=new linkList;  //创建头结点
    p=head;
    for(i=1;i<n;i++)
    {
       q=new linkList;
       q->data=i;
       q->next=NULL;
       p->next=q;
       q->prior=p;  
       p=q;   //头结点后移
       
    }
    
}

d）链表插入

void insert(Dlinklist &head, int n, int x)	//在i的位置插入数据x
{ 
     int j=0;
     Dlinklist s,L;
     L=head;
     while(L&&j<n-1)
     {
        j++;
        L=L->next;     
     }
     if(L!=NULL)
     {
         s=new linkList;
         s->data=x;
         s->next=L->next;
         if(L->next)
         L->next->prior=S;
         s->prior=L;
         L->next=s;
         
     }
     
}
  • 链表的插入和链表创建过程相似

f）链表删除

void delete(Dlinklist &head, int i)
{
	Dlinklist L = head, s;
	int j = 0;
	while(j < i - 1 && L)
	{
		j++;				//寻找正确的删除位置 
		L = L -> next;		//指针后继 
	}

	if(L)
	{
		s = L -> next;  	//s指向要删除节点的后继节点
		if(!s)				//如果没有后继节点 
			puts("删除失败");	
		L -> next = s -> next;	//从链表中删除要删除的节点
		if(!L -> next)		//如果存在后继节点
		L -> next -> prior = L;  
		delete s;			//释放要删除的节点

	} 
}

四：循环单链表

  • 带头结点的循环单链表的各种操作算法与带头结点单链表的算法实现类似，差别仅在于算法判别当前节点p是否为尾节点的条件不同。单链表中的判别条件为p！=NULL或p->next!=NULL，而单循环链表判别条件是p！=L或p->next!=L;在循环单链表中，找开始节点和尾节点的存储位置分别是rear->next->next(带头结点)和rear

a)循环单链表结构体定义

typedef struct Node
{
   int data;
   struct Node *next;
   
}Node,*LinkList;

b)建立循环单链表

void CreateLinkList(LinkList L)
{
   LinkList *rear,*s;
   rear=L; //尾指针指向当前表尾，其初始值指向头结点
   int flag=1;
   int x;
   while(flag)
   {
       cin>>x;
       if(x!=0)
       {
         s=new struct Node;
         s->data=x;
         rear->next=s;    //尾插法
         rear=s;
       }
       else
       {
          rear->next=L;
          flag=0;
       }
   }
}

c)删除节点

void Delete(LinkList L,int x)
{
  LinkList p,r;
  p=L;
  int k=0;
  while(p->next!=L&&p->data<x)
  {
     p=p->next;
     k++;
  }
   
   while(p->next==L)
   {
      cout<<"非法删除"
      return ;
   }
   r=p->next;
   p->next=r->next;
   delete r;
}
  • 单循环链表的插入和删除操作的步骤是差不多的，不过这里要注意的while里的条件发生变化，不再是p->nextNULL,而是p->nextL

d）循环单链表的合并

CLLinkList MergeCLLinkList(CLLinkList CL_a,CLLinkList CL_b)
{
    LinkList p ,q;
    p=CL_a;
    q=CL_b;
    while(p->next!=CL_a)//找到LA的表尾，用p指向它 
        p=p->next;
    while(q->next!=CL_b)//找到LB的表尾，用q指向它
        q=q->next;
    q->next=CL_a;//修改LB的表尾指针，使之指向表LA的头结点 
    p->next=CL_b->next;    //修改LA的表尾指针，CL_b->next的意思是跳过CL_b头结点
    delete CL_b;
    return CL_a;
}

1.2对线性表的认识和体会

对线性表中，数组是我们上学期一直接触的东西，链表，则是我们在期末匆匆学习的一块，对其并没有深入练习，但是，因为我上学期的课设是用链表做的，所以我上学期就对链表的基本操作有一定的了解，记得当时刚学习链表的时候，上课老师讲的其实完全听不懂，因为对节点的理解感觉很抽象，以及节点的next指针域，后来我就去看了视频，研究了一段时间，再加上了最后的课设练习，才会了，虽然有点慢，但是也是因为有了基础，这学期开始才不至于落下，学链表，其实有一个一直愿意去搞懂的东西，也经常因为这个，代码会报错，就是p指针什么时候为会为空，每次都是跟着感觉来，大不了再改一次这样的想法，虽然结果最后会正确，但是该懂得地方依然懵懂，所以每次如果是太细的题目，我就开始犹豫，到底是p还是p->next。

2.PTA实验作业

2.1 题目 ：6-8 jmu-ds-链表倒数第m个数

题目：

已知一个带有表头节点的单链表，查找链表中倒数第m个位置上的节点。

  • 输入要求：先输入链表结点个数，再输入链表数据，再输入m表示倒数第m个位置。
  • 输出要求，若能找到则输出相应位置，要是输入无效位置，则输出-1。

输入样例：

5
1 2 3 4 5
2

输出样例：

4

2.1.1代码截图

法一：

法二：

2.1.2 PTA提交列表和说明

法一：

法一：

Q1:部分正确
测试点中有两个是关于位置无效的，一个是链表为空，一个是m无效，当时是第三个测试点一直过不去，脑子里想的是m无效，那么当m大于链表长度时即无效，但是还少了一种情况，就是m=0的时候
Q2:编译错误
改代码时并没有在编译器跑一遍，二姐复制，可能哪里多了个字符吧
Q3：段错误
指针指向空

法二：

Q1:部分正确
因为是临时想多加的方法，所以写完之后，放到pta里，依旧是二三测试点没有过，二测试点好过，第三个测试点，又想了一点时间
Q2:部分正确
第三个测试点是如果m大于链表长度时，如果target_p没有动过的话，就是无效

2.2题目：7-1 两个有序链表序列的交集

题目：

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。

输入格式：

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式：

在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例：

1 2 5 -1
2 4 5 8 10 -1

输出样例：

2 5

2.2.1代码截图：

2.2.2 PTA提交列表和说明

Q1:最后遍历输出链表时，忘记L3=L3->next了

2.3 题目：7-2 重排链表

题目：

给定一个单链表 L1→L2→⋯→L**n−1→L**n，请编写程序将链表重新排列为 L**n→L1→L**n−1→L2→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤105)。结点的地址是5位非负整数，NULL地址用−1表示。

接下来有N行，每行格式为：

Address Data Next

其中Address是结点地址；Data是该结点保存的数据，为不超过105的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出格式：

对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例：

68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1

2.3.1同学代码截图

思路步骤一：

	for (i = 0; i < fre; i++)	//输入数据
	{
		cin >> idx;
		cin >> ssl[idx].data >> ssl[idx].next;
	}
ssl下标 ssl.data ssl.next
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 0
99999 5 68237
12309 2 33218

思路步骤二：

	for (i = head; i != -1; i = ssl[i].next)	//获取静态表的逻辑顺序
	{
		address.push_back(i);
	}
address下标 address值
0 00100
1 12309
2 33218
3 0
4 99999
5 68237
6 -1

100->12309->33218->0->99999->68237->-1

思路步骤三：

	for (i = 0; i < fre / 2; i++)	//重排链表,fre=6
	{
		ssl[address[fre - i - 1]].next = address[i];
		ssl[address[i]].next = address[fre - i - 2];
	}
	if (fre % 2 == 0)	//修改表尾元素的后继为 NULL
		ssl[address[fre / 2 - 1]].next = -1;
	else
		ssl[address[fre / 2]].next = -1;
i fre-i-1 fre-i-2 add[fre-i-1] add[i] add[fre-i-2]
0 5 4 68237 100 99999
1 4 3 99999 12309 0
2 3 2 0 33218 -1

68237->100->99999->12309->0->33218->-1

2.3.2 PTA提交列表和说明

Q1:编译错误
发现问题时，在pta里面直接改，所以有些问题看不出来
Q2：多种错误
代码思路不清，所以过不了，我觉得这道题要列表比较清楚一点，不至于乱掉，所以借鉴的是同学的代码，思路比较清晰，更容易以后再看这道题时理解

3.阅读代码

链表

3.1题目及解题代码

题目：

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

样例输入：

1->2->3->4->5->NULL, k = 2

样例输出：

4->5->1->2->3->NULL

解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

解题代码：

3.1.1问题思路

  1. 这道题目的关键在于找到 尾节点和旋转后新链表的尾节点。
    假设是 tail, new->tail.
    然后只要进行 tail->next = head;

                    head = new_tail->next;

                new_tail->next = NULL;

  2. 找两个尾节点可以采用 双指针的方法。

注意到 这两个节点 间距是 K，（初始化，tail = new_tail = head;）

STEP 1：tail 从 head 出发，先走 k 步

STEP 2: new_tail 和 tail 同时往前走， 当 tail 指向尾节点时， new_tail 的位置即所求。

时间复杂度和空间复杂度

时间复杂度是O（n），空间复杂度是O(1)

3.1.2伪代码

ListNode *ReverseKLisr(ListNode*head,int k)
{ 
    对k进行处理
    如果大于链表的长度，则求余
    小于，则加上原来的长度
    
     for i=0 to i<k
     tail指针走k步
     end for

     while(tail->next)
     { 
         tail指针和new_tail指针一起走
     }
     
      让tail->next指向head
      head则是new_tail的下一个节点
      new_tail->next是新的尾节点，指向空

3.1.3运行结果

3.1.4题目解题优势及难点

这道题的类型和数组右移或左移看似题目好像差不多，但是思路其实又不一样，数组右移这种，在我看来，如果复杂起来，会很复杂，但是简单起来，也可以很简单，就是思路不一样，这道题比较巧妙的就是两个指针，tail指针遍历整个链表，但是new_tail指针式在合适的时候跟着移动，可以大大减少时间复杂度，其实在PTA里有一道题，寻找链表倒数m个位置这题，用这个思路，也可以很快找到，就不用两次去遍历链表，可能不用完整遍历就可以找到

减枝算法：

通过分析问题，发现判断条件，避免不必要的搜索，提前减少不必要的搜索路径

3.2题目及解题代码

题目：

乔治拿出同样长的棍子，随意地剪，最后棍子的总数量少于50。现在他想把棍子还原成原来的状态，却忘了原来有多少根棍子，也忘了原来有多少根棍子。请帮助他，并设计一个程序，计算尽可能最小的原始长度的这些棍子。以单位表示的所有长度都是大于零的整数。

输入格式

输入包含2行块。第一行包含切割后的棒件数量，最多有64根。第二行包含用空格分隔的部分的长度。文件的最后一行包含零。

输出格式

输出应该包含最小的原始棒的长度，每一行一个。

样例输入：

9

5 2 1 5 2 1 5 2 1

样例输出：

6

解题代码：


3.2.1问题思路

题目意思：
乔治开始拿了a个长度均为L的木棍，随机锯木棍，最终把这a个木棍锯成了n个小块。根据n个小块及其各自长度，求出L可能的最小值

img

img

时间复杂度和空间复杂度

首先对时间复杂度进行分析，主要的是在第二个for循环里，但是这个的时间复杂度我觉得很复杂，我不会算，但是这个是空间复杂度是O（1）

3.2.2伪代码

全局变量
a[max]存放木块
vis[max]用来判断是否已匹配的标志
定义 maxed 还没剪之前，一样的长度的木棍的可能数量，
len,是木块的数量，sum,木块的总长度
int main()
{
    for i=0 to i<len
    对a[i]进行赋值，存放木块的长度
    并对a[i]进行求和，存放到sum里
    end for
    
    sort()对a[]这个数组进行从大到小排序
    
    开始进行枚举
    
    for i=a[0] to i<sum/2 //因为最大长度是整数，所以不会超过总长度的一半   
    if（sum%i==0)  //猜测可能的木棍的长度
    
       用memsert对数组vis进行初始化为0     
       还没剪时相同长度木棍的数量maxed=sum%i;
       if(dfs(0,0,0,i))
          输出长度，即为所求
       end if     
      end if
     end for      
       
}
通过dfs判断是否可以拼凑成长度为k的木块
sum当前正在拼凑的木块已有的长度，
cur为目前搜索的位置
res为已拼成的木棍的数量，
k为假设的单个木块的长度
bool dfs(int sum,int cur,int res,int k)
{
   if(res==maxed)//已拼成的木棍数量等于猜测的木棍数量
      reurn true;
      
   for i=cur to i<len
     如果第i个木棍已经计入，或者与前一个木棍等长并同样未计入，则跳过
   if(vis[i]||(i&&a[i]==a[i-1]&&vis[i-1]))
        continue;
   end if
   
     if(a[i]+sum==k)  如果已拼好的木棍长度等于猜测的单个木棍长度
      vis[i]=1;表示这个数已经访问过
         if(dfs(0,0,0,res+1,k))//这一步表示拼成已一根长度为k的木块，再去拼下一根
         return true;  
      vis[i]=0;//虽拼成了长度为k的木块，但是剩下的木块不能成功，所以回溯失败
      return false;
   end if
   
   if(a[i]+sum<k)   //没拼好，则继续找
       vis[i]标志为1
         if(dfs(a[i]+sum,i+1.res.k))原来长度加上a[i],从下一位置开始搜索
         return true;
       vis[i]=0;
         if(!sum)
          return false;//最后不能拼凑成功
   end if
  end for
  
}

3.2.3运行结果

在递归里面加了打印语句，看的更清楚一点

3.2.4题目解题优势及难点

首先，这道题目，是对时间复杂度的考验，如何减少不必要的搜索是我们需要考虑的，例如下面对剪枝条件的分析，无论少了哪一条，都可能使程序运行的时间大大增加，并且，这道题分治思想的巧妙运用也是我们应该学会的，将大问题分成不同重复的小问题，对于递归，如何学会控制参数，以及其中的条件设置，对我而言，都是难点。

剪枝条件分析：

1.a为整数，故初始长度L一定是减下来以后所有木棍总长度sum的因数

2.n个小木块中，长度长的木块凑成L长的搭配的可能性更小，所以将n个木块从大到小排序，从大的开始搜索，

3.搜索过程是按照已经排序好的顺序，所以前一个木棍没有成功，这一个也一定不能成功，直接略过

4.当一个木块拼凑失败，不在按这个条件进行搜索

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/-sushi/p/12366254.html