ds_2

data_structure01

顺序表

`typedef struct Sqlist{

 int data[maxSize];

 int length;

}Sqlist;`

## 单链表

单链表

`typedef struct LNode{

 int data;

 struct LNode *next;

}LNode,*LinkList;`

双链表

typedef struct DLNode {

 int data;

 struct DLNode *prior;

 struct DLNode *next;

}DLNode,*DLinkedList;

Q1元素逆置

设计⼀个⾼效算法，将顺序表L中所有元素逆置，要求算法的空间复杂度为O(1)

`void Reverse(int r[],int left,int right)

{//将数组R中的数据原地逆置

 	int i=left; int j=right; int temp;//i等于左边界left, j等于右边界

right,temp为辅助变量

 	while(i<j)

	 {//交换r[i]与r[j]的值

			 temp=r[i];

			 r[i]=r[j];

			 r[j]=temp;

 			i++; //i右移⼀个位置

			 j--; //j左移⼀个位置

 }

}`

Q2 q1例题

设将n(n>1)个整数存放到⼀维数组R中。试设计⼀个在时间和空间两⽅⾯都尽可能⾼

效的算法，将R中保存的序列循环左移p (0<p<n)个位置，即将R中的数据由(x0, x1，…

,xn-1)变换为(xp，xp+1，…, xn-1,x0,x1，…，xp-1)，并计算时间和空间复杂度。

思路：设前(n-p)个元素为A，后p个元素为B，则初始序列表示为AB，⽬标序列为BA。可通过AB逆置成(AB)-1=(B-1A-1),再分别将B和A逆置，最终可得到序列BA。先将n个数据x0, x1，… xn-1原地逆置，得到xn-1，… ，x1, x0，然后再将前n-p个数据和后p个数据分别原地逆置，得到最终结果:xp，xp+1，…, xn-1,x0,x1，…，xp-1。

/*原地逆置*/
void Reverse(int r[],int left,int right)
{//将数组R中的数据原地逆置
	 i=left; j=right; //i等于左边界left, j等于右边界right
	 while(i<j)
		{//交换r[i]与r[j]的值
             temp=r[i];
             r[i]=r[j];
             r[j]=temp;
             i++; //i右移⼀个位置
             j--; //j左移⼀个位置
 		}
}
/*移位函数*/
void LeftShift(int r[],int n,int p)
{//将⻓度为n的数组R中的数据循环左移p个位置
     if (p>0&&p<n)
     {
         Reverse(r,0,n-1); //将全部数据逆置
         Reverse(r,0,n-p-1); //将前n-p个数据逆置
         Reverse(r,n-p,n-1); //将后p个数据逆置
     }
}

###Q3

已知线性表（a1,a2,…,an）按顺序结构存储且每个元素为不相等的整数。设计把所

有奇数移动到所有偶数前边的算法。例如，A=（1,2,3,4,5,6,7），移动后变为A=

（1,7,3,5,4,6,2）（要求时间最少，辅助空间最少）。

思路：对于顺序表L，从左向右找到偶数L.data[i]，从右向左找到奇数L.data[j]，将两者交换。循环这个过程直到i⼤于j为⽌。

void Move(SqList &L)
{
     int i = 0, j = L.length-1, k;
     ElemType temp;
     while(i < j)
     {
         while(L.data[i]%2 == 1 && i<=L.length-1)
        	 i++; //i指向⼀个奇数
         while(L.data[j]%2 == 0 && j>=0)
         	j--; //j指向⼀个偶数
         if(i < j)
         {
             temp = L.data[i]; //交换L.data[i]和L.data[j]
             L.data[i] = L.data[j];
             L.data[j] = temp;
         }
     }
}

Q4

将两个有序表合并为⼀个新的有序顺序表，并由函数返回结果顺序表。

思路：由于顺序表有序，则先按顺序不断取下两个顺序表表头较⼩的结点存⼊新的顺序表中。然后，通过⽐较两个顺序表的⻓度，看哪个表还有剩余，将剩下的部分加到新的顺序表后⾯

bool Merge (SqList A, SqList B, SqList &C) {
//将有序顺序表A与B合并为⼀个新的有序顺序表C
     if (A.length+B.length>C.maxSize) //⼤于顺序表的最⼤⻓度
     	return false;
     int i=0 j=0,k=0;
     while (i<A.length&&j<B.length) {
     //循环，两两⽐较，⼩者存⼊结果表
         if (A.data[i]<=B.data[j])
         	C.data[k++]=A.data[i++] ;
         else
        	 C.data[k++]=B.data[j++] ;
        }
     while (i<A.length)
     //还剩⼀个没有⽐较完的顺序表
   	 		C.data[k++]=A.data[i++] ;
     while (j<B.length)
    		 C.data[k++]=B.data[j++] ;
     C.length=k;
     return true;
}

Q5

设计⼀个算法，从⼀给定的顺序表L中删除元素值在x到y(x≤y)之间的所有元素，要求

以较⾼的效率来实现，空间复杂度为O(1)。

思路：此题的关键点在于:在时间复杂度为O(n)、空间复杂度为O(1)条件的限定下，不能另开辟空间，且只能通过遍历⼀趟顺序表来完成。则⽤k记录顺序表中值不在x到y(x≤y)之间的元素个数，k初始为0。可以采⽤类似建⽴顺序表的思想，从前向后遍历顺序表，查找值不在区间的元素，如果找到，则利⽤原表的空间记录这些元素，同时使k增1。遍历结束后，顺序表中前k个元素即为值不在区间内的元素，最后将顺序表的⻓度置为k。

void Del_xy(SqList &L, int x, int y)
{
 	int i = 0, k = 0; //i为遍历下标，k为保留元素下标
 	while(i<L.length)
 	{
 		if(L.data[i] < x || L.data[i] > y)
 			L.data[k++] = L.data[i]; 
 		i++;
 	}
 	L.length=k;
}

Q6

试编写算法将带头结点的单链表就地逆置，所谓“就地”是辅助空间复杂度为O(1)。（头插法）

思路：将头结点摘下，然后从第⼀结点开始，⼀次插⼊到头结点的后⾯（头插法建⽴单链表），直

到最后⼀个结点为⽌，这样就实现了链表的逆置

LinkList Reverse(LinkList L)
{
 //L是带头结点的单链表，本算法将L逆置
 LNode *p, *r; //p为⼯作指针，r为p的后继，以防断链
 p = L->next; //从第⼀个元素结点开始
 L->next = NULL; //先将头结点L的next域值为NULL
 while(p != NULL) //依次将元素结点摘下
 {
     r = p->next; //暂存p的后继
     p->next = L->next;//将p结点插⼊到头结点之后
     L->next = p;
     p = r;
 }
 return L;
}

Q7

将⼀个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中中含有原

标中序号为奇数的元素，⽽B表中含有原表中序号为偶数的元素，且保持其相对顺序不

变（尾插法）

LinkList DisCreat(LinkList A)
{
     //将A表中结点按照序号的奇偶性分解到表A或者表B中
     int i = 1; //i记录表A中结点的序号
     LinkList B = (LinkList)malloc(sizeof(LNode)); //创建B表表头
     B->next = NULL; //B表初始化
     LNode *ra = A, *rb = B; //ra和rb将分别指向将创建的A表和B表的尾节点
     p = A->next;
     A->next = NULL; //将A表置空
     while(p != NULL)
     {
         if(i % 2 == 0) //处理序号为偶数的链表结点
         {
             rb->next = p; //在表尾插⼊新结点
             rb = p; //rb指向新尾结点
         }
         else
         {
             ra->next = p; //处理原序号为奇数的结点
             ra = p; //在A表尾插⼊新的结点
          }
         p = p->next; //将p恢复为指向新的待处理结点
         i++; //序号+1
   	  }
     ra->next = NULL;
     rb->next = NULL;
     return B;
 }

Q8

试编写在带头结点的单链表L中删除⼀个最⼩值结点的⾼效率算法（假设最⼩值结点

是唯⼀的）

思路：⽤p从头⾄尾扫描单链表，pre指向p结点的前驱，⽤minp保存值最⼩的结点指针（初值为p）,minpre*指向minp结点的前驱（初值为pre）。⼀遍扫描，⼀边⽐较，若p->data⼩于minp-data，则将p、pre分别赋值给minp，minpre，如下图所示。当p扫描完毕，minp指向最⼩值结点，minpre指向最⼩值结点的前驱结点，再将minp所指结点删除即可。

LinkList Delete_Min(LinkList L)

{

     //L是带头结点的单链表，本算法是删除其最⼩值结点

     LNode *pre = L, *p = pre->next; //p为⼯作指针，pre指向其前驱

     LNode *minpre = pre, *minp = p; //保存最⼩值结点及其前驱

     while(p != NULL)

     {

         if(p->data < minp->data)

         {

             minp = p;

             minpre = pre;

      	     }

             pre = p; //继续扫描下⼀节点

             p = p->next; 

         }

         minpre->next = minp->next; //删除最⼩值结点

         free(minp);

         return L;
	
	}

Q9

如果⼀个序列是⼀个先单调递增后单调递减的序列，那么它称为双调序列。例如序

列{1，4，6，8，3，-2}就是⼀个双调序列。设计⼀个尽可能⾼效的算法，找到由N个数

组成的⼀个双调序列中最⼤的关键值。要求：

1）描述算法的基本设计思想；

2）根据设计思想，采⽤ C 或 C++语⾔描述算法，关键之处给出注释；

3）说明你所设计的算法的时间复杂度和空间复杂度。

//题⽬没有说明是否严格单调递增，所以重复元素越多效率越低，最坏O(n)，⽆重复元素
log2(n),
//⽆重复元素可以使⽤⾮递归空间消耗更少.
int find_max(int low, int high, int[] a){
     int mid;
     while(low < high){
     mid = (high-low)/2 + low; //取中，左端点，防⽌溢出
     if(a[mid] < a[mid+1]) //仍在上升区间，丢弃左边
     	return find_max(mid+1, high, a);
     else if(a[mid] > a[mid+1]) //在下降区间，丢弃右边
     	return find_max(low, mid, a);
     else
    	 return max(find_max(low, mid, a), find_max(mid+1, high, a));
         //⽆法知道升降区间，分为两部分递归判定取最⼤值
     }
     return a[low];
}