正文

[Algorithm]线性表

IP云
IP云V管理员/4 阅读
09/27
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

一. 线性表基础算法

1.线性表插入操作

1 // 线性表插入操作(在第i(1≤i≤L.length+1)个位置上插入新元素elem)
2 bool InsertSeq( SeqList& L, int i, ElemType elem )
3 {
4 if ( i < 1 || i>L.length + 1 || L.length >= MAXSIZE )
5 return false;
6 for ( j = L.length - 1; j >= i - 1; j-- )
7 L.elem[j + 1] = L.elem[j];
8 L.elem[j + 1] = elem;
9 L.length++;
10 return true;
11 }

说明:

  • 插入操作: 可选位置为1≤i≤L.length+1
  • 最好情况: 表尾(i=n+1)插入, O(1)
  • 最坏情况: 表头(i=1)插入, O(n)
  • 平均情况: 设 $Pi=\frac {1}{(n+1)}$ 是在第i个位置插入一个结点的概率,则在长度为n的线性表中插入一个结点所需的移动结点的平均次数为$\frac{n}{2}$次,即O(n): $$\sum_{i=1}^{n+1} Pi\cdot{(n+1-i)}=\frac{1}{n+1}\cdot\sum_{i=1}^{n+1} {(n-i+1)}=\frac{1}{n+1}\cdot\frac{n(n+1)}{2}=\frac{n}{2}$$

2.线性表删除操作

1 bool DeleteSeq( SeqList& L, int i, ElemType& elem )
2 {
3 for ( i<1 || i>L.length ) return false;
4 elem = L.elem[i - 1];
5 for ( j = i; j < L.length; j++ )
6 L.elem[j - 1] = L.elem[j];
7 L.length--;
8 return true;
9 }

  • 最好情况: 删除表位(i=n),O(1)
  • 最坏情况: 删除表头(i=1),O(n)
  • 平均情况: 设$Pi=\frac{1}{n}$是删除第i个位置上结点的概率,则在长度为n的线性表中删除一个结点所需移动结点的平均次数为$\frac{n-1}{2}$次,即O(n):$$\sum_{i=1}^{n}Pi\cdot{(n-i)}=\frac{1}{n}\sum_{i=1}^{n}{(n-i)}=\frac{1}{n}\cdot\frac{n(n-1)}{2}=\frac{n-1}{2}$$

3.线性表查找操作

1 int LocateSeq( SeqList& L, ElemType elem )
2 {
3 for ( i = 0; i < L.length; i++ )
4 if ( L.elem[i].key == elem.key )
5 return i + 1;
6 return 0;
7 }

  • 最好情况: 查找到表头,O(1)
  • 最坏情况: 查找到表尾,O(n)
  • 平均情况: 设$Pi=\frac{1}{n}$是查找元素在第i(1≤i≤L.length)个位置上的概率,则在长度为n的线性表中查找值为elem的元素所需比较的平均次数为$\frac{n+1}{2}$次,O(n):$$\sum_{i=1}^{n}Pi\cdot{i}=\frac{1}{n}\cdot\sum_{i=1}^{n}{i}=\frac{1}{n}\cdot\frac{n(n+1)}{2}=\frac{n+1}{2}$$

二.线性表综合应用

1.删除线性表中所有值为x的数据元素

1 bool DeleteX( SeqList& L, ElemType x )
2 {
3 int k = 1;
4 for ( i = 1; i <= L.length; i++ )
5 if ( L.elem[i].key != x.key )
6 L.elem[k++] = L.elem[i];
7 L.length = k;
8 return true;
9 }

2.从有序顺序表中删除值在[s,t]的所有元素

1 bool DeleteS2TOrderedSeq( SeqList& L, int s, int t )
2 {
3 for ( i = 1; i <= L.length&&L.elem[i].key < s; i++ ); // 找≥s的第一个元素
4 for ( j = i; j <= L.length&&L.elem[j].key <= t; j++ ); // 找>t的第一个元素
5 while ( j <= L.length )
6 L.elem[i++] = L.elem[j++];
7 L.length = i;
8 return true;
9 }

3.从顺序表中删除值在[s,t]的所有元素

1 bool DeleteS2TSeq( SeqList& L, int s, int t )
2 {
3 int k = 1;
4 for ( i = 1; i <= L.length; i++ )
5 if ( L.elem[i].key<s || L.elem[i].key>t )
6 L.elem[k++] = L.elem[i];
7 L.length = k;
8 return true;
9 }

4.从有序顺序表中删除所有值重复的元素

1 bool DeleteSameOrderedSeq( SeqList& L )
2 {
3 int k = 1;
4 for ( i = 2; i <= L.length; i++ )
5 if ( L.elem[i].key != L.elem[k].key )
6 L.elem[++k] = L.elem[i];
7 L.length = k;
8 return true;
9 }

5.将两个有序顺序表合并为一个新的有序顺序表

1 bool Merge( SeqList A, SeqList B, SeqList& C )
2 {
3 int i = 1, j = 1, k = 1;
4 while ( i<=A.length&&j<=B.length )
5 {
6 if ( A.elem[i].key <= B.elem[j].key )
7 C.elem[k++] = A.elem[i++];
8 else
9 C.elem[k++] = B.elem[j++];
10 }
11 while ( i <= A.length ) C.elem[k++] = A.elem[i++];
12 while ( j <= B.length ) C.elem[k++] = B.elem[j++];
13 C.length = k - 1;
14 return true;
15 }

6.原数组A[m+n]={a1,a2,...,am,b1,b2,...,bn},现要求转变为A[m+n]={b1,b2,...,bn,a1,a2,...,am}

1 // 元素倒置
2 void Reverse( ElemType A[], int s, int e )
3 {
4 for ( i = s; i < ( s + e ) / 2; i++ )
5 swap( A[i], A[s + e - i - 1] );
6 }
7
8 void ExChange( ElemType A[], int m, int n )
9 {
10 Reverse( A, 0, m );
11 Reverse( A, m, m + n );
12 Reverse( A, 0, m + n );
13 }

7.线性表(a1,a2,...,an)递增有序,设计算法花最少时间找到数值为x的元素:

1)找到,则与其后继元素位置互换

2)未找到,将其插入表中并使表中元素仍然递增有序

1 // 使用折半查找的方法
2 void SearchExchangeInsert( ElemType A[], int n, ElemType x )
3 {
4 int low = 1, high = n;
5 while ( low <= high )
6 {
7 mid = ( low + high ) / 2;
8 if ( x.key == A[mid].key )
9 {
10 if ( mid != n )
11 swap( A[mid], A[mid + 1] );
12 return;
13 }
14 else if ( x.key < A[mid].key ) high = mid - 1;
15 else low = mid + 1;
16 }
17 for ( j = n; j >= high + 1; j-- )
18 A[j + 1] = A[j];
19 A[j + 1] = x;
20 }

8.设计算法将一维数组R中的序列循环左移p(0<p<n)个位置(算法思想和⑥相同)

1 // 元素倒置
2 void Reverse( ElemType A[], int s, int e )
3 {
4 for ( i = s; i < ( s + e ) / 2; i++ )
5 swap( A[i], A[s + e - i - 1] );
6 }
7
8 void ShiftLeft( ElemType R[], int n, int p )
9 {
10 Reverse( R, 0, p );
11 Reverse( R, p, n );
12 Reverse( R, 0, n );
13 }

9.长度为L(L≥1)的升序序列S,处在$\lceil\frac{L}{2}\rceil$个位置的数成为S的中位数,设计一个在时空都尽量高效的算法找出两个等长序列A和B的中位数

1 int FindMidFromABOrderedSeq( int A[], int B[], int n )
2 {
3 int s1, s2, e1, e2, m1, m2;
4 s1 = s2 = 0;
5 e1 = e2 = n - 1;
6 while ( s1 != e1 || s2 != e2 )
7 {
8 m1 = ( s1 + e1 ) / 2;
9 m2 = ( s2 + e2 ) / 2;
10 if ( A[m1] == B[m2] )
11 return A[m1];
12 else if ( A[m1] < B[m2] )
13 {
14 if ( !( ( s1 + e1 ) % 2 ) )
15 s1 = m1, e2 = m2;
16 else
17 s1 = m1 + 1, e2 = m2;
18 }
19 else
20 {
21 if ( !( ( s2 + e2 ) % 2 ) )
22 s2 = m2, e1 = m1;
23 else
24 s2 = m2 + 1, e1 = m1;
25 }
26 }
27 return A[s1] < B[s2] ? A[s1] : B[s2];
28 }

三.线性表的链式表示

1.采用头插法建立单链表

1 LinkList CreateList( LinkList& L )
2 {
3 L = ( LinkList ) malloc( sizeof( LNode ) );
4 L->next = NULL;
5 scanf( "%d", &x );
6 while ( x != 9999 )
7 {
8 s = ( LNode* ) malloc( sizeof( LNode ) );
9 s->data = x;
10 s->next = L->next;
11 L->next = s;
12 scanf( "%d", &x );
13 }
14 return L;
15 }

2.采用尾插法建立单链表

1 LinkList CreateList( LinkList& L )
2 {
3 L = ( LinkList ) malloc( sizeof( LNode ) );
4 L->next = NULL;
5 r = L;
6 scanf( "%d", &x );
7 while ( x != 9999 )
8 {
9 s = ( LNode* ) malloc( sizeof( LNode ) );
10 s->data = x;
11 r->next=s;
12 r = s;
13 scanf( "%d", &x );
14 }
15 r->next = NULL;
16 return L;
17 }

四.线性表相关综合算法

1.递归删除不带头结点的单列表L中所有值为x的结点

1 void DeleteX( LinkList& L, ElemType x )
2 {
3 if ( !L ) return;
4 if ( L->data == x )
5 {
6 q = L;
7 L = L->next;
8 free( q );
9 DeleteX( L, x );
10 }
11 else
12 DeleteX( L->next, x );
13 }

2.删除带头结点的单链表L中所有值为x的结点

1 void DeleteX( LinkList& L, ElemType x )
2 {
3 pre = L;
4 p = L->next;
5 while ( p )
6 {
7 if ( p->data == x )
8 {
9 q = p;
10 pre->next = p->next;
11 p = p->next;
12 free( q );
13 }
14 else
15 {
16 pre = p; p = p->next;
17 }
18 }
19 }

3.反向输出带头结点的单链表L的每个结点的值

1 void PrintX( LinkList L )
2 {
3 if ( !L )return;
4 PrintX( L->next );
5 visit( L );
6 }

4.删除带头结点单链表L中最小值结点

1 LinkList DeleteMin( LinkList& L )
2 {
3 LinkList p, s, pre, q;
4 p = s = L->next;
5 pre = q = L;
6 while ( p )
7 {
8 if(p->data<s->data )
9 {
10 s = p; q = pre;
11 }
12 pre = p;
13 p = p->next;
14 }
15 q->next = s->next;
16 free( s );
17 return L;
18 }

5.将带头结点的单链表就地逆置,"就地"指辅助空间复杂度为O(1)

1 LinkList Reverse( LinkList L )
2 {
3 LinkList p, q;
4 p = L->next;
5 L->next = NULL;
6 while ( p )
7 {
8 q = p->next;
9 p->next = L->next;
10 L->next = p;
11 p = q;
12 }
13 return L;
14 }

6.将带头结点的单链表L排序,使其递增有序

1 void InsertSort( LinkList& L )
2 {
3 LinkList p, pre, r;
4 p = L->next; r = p->next;
5 p->next = NULL; p = r;
6 while ( p )
7 {
8 r = p->next;
9 pre = L;
10 while ( pre->next&&pre->next->data < p->data )
11 pre = pre->next;
12 p->next = pre->next;
13 pre->next = p;
14 p = r;
15 }
16 }

7.在带头结点的单链表中,删除值介于(s,t)之间的元素

1 void DeleteS2T( LinkList& L, int s, int t )
2 {
3 LinkList pre, p;
4 pre = L; p = pre->next;
5 while ( p )
6 {
7 if ( p->data > s && p->data < t )
8 {
9 pre->next = p->next;
10 free( p );
11 p = pre->next;
12 }
13 else
14 {
15 pre = p;
16 p = p->next;
17 }
18 }
19 }

8.找出两个单链表的公共结点

1 LinkList SearchCommon( LinkList L1, LinkList L2 )
2 {
3 LinkList pA, pB;
4 int lenA, lenB, dist;
5 pA = L1->next, pB = L2->next;
6 lenA = lenB = 0;
7 while ( pA ) { pA = pA->next; lenA++; }
8 while ( pB ) { pB = pB->next; lenB++; }
9 pA = L1->next, pB = L2->next;
10 if ( lenA > lenB )
11 {
12 dist = lenA - lenB;
13 while ( dist-- ) pA = pA->next;
14 }
15 else
16 {
17 dist = lenB - lenA;
18 while ( dist-- ) pB = pB->next;
19 }
20 while ( pA )
21 {
22 if ( pA == pB ) return pA;
23 pA = pA->next, pB = pB->next;
24 }
25 return NULL;
26 }

9.带表头结点的单链表,按递增次序输出单链表中各结点的数据元素,并释放空间

1 void AscDelete( LinkList& L )
2 {
3 LinkList p, s, pre, r;
4 while ( L->next )
5 {
6 s = p = L->next; r = pre = L;
7 while ( p )
8 {
9 if ( p->data < s->data )
10 {
11 s = p; r = pre;
12 }
13 pre = p;
14 p = p->next;
15 }
16 r->next = s->next;
17 visit( s );
18 free( s );
19 }
20 free( L );
21 }

10.将带头结点的单链表A分解成两个带头结点的单链表A和B,A中含有奇数序号元素,B中含有偶数序号元素且相对位置不变

1 // 法一
2 LinkList Split( LinkList& A )
3 {
4 LinkList p, B, rA, rB;
5 int i = 0;
6 p = A->next;
7 B = ( LinkList ) malloc( sizeof( LNode ) );
8 rA = A; A->next = NULL;
9 rB = B; B->next = NULL;
10 while ( p )
11 {
12 i++;
13 if (i%2)
14 {
15 rA->next = p; rA = p;
16 }
17 else
18 {
19 rB->next = p; rB = p;
20 }
21 p = p->next;
22 }
23 rA->next = NULL;
24 rB->next = NULL;
25 return B;
26 }
27
28 // 法二
29 LinkList Split( LinkList& A )
30 {
31 LinkList p, B, rB, pre;
32 int i = 0;
33 B = ( LinkList ) malloc( sizeof( LNode ) );
34 rB = B;
35 pre = A; p = pre->next;
36 while ( p )
37 {
38 i++;
39 if ( i % 2 == 0 )
40 {
41 pre->next = p->next;
42 rB->next = p;
43 rB = p;
44 p = pre->next;
45 }
46 else
47 {
48 pre = p;
49 p = p->next;
50 }
51 }
52 return B;
53 }

11.C={a1,b1,a2,b2,...,an,bn}为线性表,带有头结点,设计一个就地算法将其拆分为两个线性表,使A={a1,a2,...,an},B={bn,...,b2,b1}

1 LinkList Split( LinkList& A )
2 {
3 LinkList B, pre, p;
4 int i = 0;
5 B = ( LinkList ) malloc( sizeof( LNode ) );
6 pre = A; p = pre->next;
7 while ( p )
8 {
9 i++;
10 if ( i % 2 == 0 )
11 {
12 pre->next = p->next;
13 p->next = B->next;
14 B->next = p;
15 p = pre->next;
16 }
17 else
18 {
19 pre = p;
20 p = p->next;
21 }
22 }
23 return B;
24 }

12.在递增有序的带头结点的单链表中,数值相同的只保留一个,使表中不再有重复的元素

1 void DeleteSame( LinkList& L )
2 {
3 LinkList p, q;
4 p = L->next;
5 while ( p )
6 {
7 q = p->next;
8 if ( q&&q->data == p->data )
9 {
10 p->next = q->next;
11 free( q );
12 }
13 else
14 p = p->next;
15 }
16 }

13.将两个按元素值递增的单链表合并为一个按元素值递减的单链表

1 void MergeList( LinkList& LA, LinkList& LB )
2 {
3 LinkList pA, pB, q;
4 pA = LA->next; pB = LB->next;
5 LA->next = NULL;
6 while ( pA&&pB )
7 {
8 if ( pA->data <= pB->data )
9 {
10 q = pA->next;
11 pA->next = LA->next;
12 LA->next = pA;
13 pA = q;
14 }
15 else
16 {
17 q = pB->next;
18 pB->next = LA->next;
19 LA->next = pB;
20 pB = q;
21 }
22 }
23 if ( pA )
24 pB = pA;
25 while(pB )
26 {
27 q = pB->next;
28 pB->next = LA->next;
29 LA->next = pB;
30 pB = q;
31 }
32 free( LB );
33 }

14.A,B为两个元素递增有序的单链表(带头结点),设计算法从A,B中公共元素产生单链表C,要求

1 void MergeList( LinkList& LA, LinkList& LB )
2 {
3 LinkList pA, pB, q;
4 pA = LA->next; pB = LB->next;
5 LA->next = NULL;
6 while ( pA&&pB )
7 {
8 if ( pA->data <= pB->data )
9 {
10 q = pA->next;
11 pA->next = LA->next;
12 LA->next = pA;
13 pA = q;
14 }
15 else
16 {
17 q = pB->next;
18 pB->next = LA->next;
19 LA->next = pB;
20 pB = q;
21 }
22 }
23 if ( pA )
24 pB = pA;
25 while ( pB )
26 {
27 q = pB->next;
28 pB->next = LA->next;
29 LA->next = pB;
30 pB = q;
31 }
32 free( LB );
33 }

15.求两个元素递增排列的链表(带头结点)A和B的交集并存放于A链表中,并释放其他结点

1 void Intersect( LinkList& LA, LinkList& LB )
2 {
3 LinkList pA, pB, r, q;
4 pA = LA->next; pB = LB->next;
5 r = LA; LA->next = NULL;
6 while ( pA&&pB )
7 {
8 if ( pA->data == pB->data )
9 {
10 r->next = pA;
11 r = pA;
12 pA = pA->next;
13 q = pB;
14 pB = pB->next;
15 free( q );
16 }
17 else if ( pA->data < pB->data )
18 {
19 q = pA;
20 pA = pA->next;
21 free( q );
22 }
23 else
24 {
25 q = pB;
26 pB = pB->next;
27 free( q );
28 }
29 }
30 r->next = NULL;
31 while ( pA )
32 {
33 q = pA;
34 pA = pA->next;
35 free( q );
36 }
37 while ( pB )
38 {
39 q = pB;
40 pB = pB->next;
41 free( q );
42 }
43 free( LB );
44 }

16.判断单链表序列B是否是A的连续子序列(不带头结点)

1 bool IsSubsequence( LinkList A, LinkList B )
2 {
3 LinkList pA, pB, h;
4 pA = A; pB = B;
5 h = pA;
6 while ( pA&&pB )
7 {
8 if ( pA->data == pB->data )
9 {
10 pA = pA->next;
11 pB = pB->next;
12 }
13 else
14 {
15 h = h->next;
16 pA = h;
17 pB = B;
18 }
19 }
20 if ( pB ) return false;
21 return true;
22 }

17.判断带头结点的循环双链表是否对称

1 bool IsSymmetry( DLinkList L )
2 {
3 DLinkList p, q;
4 p = L->next; q = L->prior;
5 while ( p != q && q->next != p )
6 {
7 if ( p->data != q->data )
8 return false;
9 p = p->next;
10 q = q->next;
11 }
12 return true;
13 }

18.将循环单链表h2链接到h1之后

1 LinkList Link( LinkList& h1, LinkList& h2 )
2 {
3 LinkList p;
4 p = h1;
5 while ( p->next != h1 )p = p->next;
6 p->next = h2;
7 p = h2;
8 while ( p->next != h2 )p = p->next;
9 p->next = h1;
10 return h1;
11 }

19.带头结点的循环链表,按递增次序输出循环链表中各结点的数据元素,并释放空间

1 void AscDelete( LinkList& L )
2 {
3 LinkList p, s, r, pre;
4 while ( L->next != L )
5 {
6 s = p = L->next; r = pre = L;
7 while ( p != L )
8 {
9 if ( p->data < s->data )
10 {
11 s = p; r = pre;
12 }
13 pre = p;
14 p = p->next;
15 }
16 visit( s );
17 r->next = s->next;
18 free( s );
19 }
20 free( L );
21 }

20.查找单链表(带头结点)中倒数第k个位置的结点,成功:则输出并返回true,否则只返回false

1 bool SearchBackwardK( LinkList L, int k )
2 {
3 LinkList p, q;
4 int count;
5 p = q = L->next;
6 count = 0;
7 while (p)
8 {
9 if ( count < k ) count++;
10 else q = q->next;
11 p = p->next;
12 }
13 if ( count < k ) return false;
14 visit( q );
15 return true;
16 }

21.链表中data绝对值相等的点,只保留第一次出现的结点($\vert{data}\vert\le{n}$)

1 void DeleteSameAbs( LinkList L, int n )
2 {
3 LinkList pre, p;
4 int *B, pos;
5 B = ( int * ) malloc( sizeof( int )*( n + 1 ) );
6 for ( int i = 0; i < n + 1; i++ )
7 B[i] = 0;
8 pre = L; p = L->next;
9 while ( p )
10 {
11 pos = p->data > 0 ? p->data : -p->data;
12 if ( B[pos] == 0)
13 {
14 B[pos] = 1; pre = p; p = p->next;
15 }
16 else
17 {
18 pre->next = p->next; free( p ); p = pre->next;
19 }
20 }
21 free( B );
22 }

22.带头结点的循环双链表递增排序

1 void AscSort( DLinkList L )
2 {
3 DLinkList p, q, r;
4 if ( !L ) return;
5 p = L->next; q = p->next; r = q->next;
6 while ( q!=L )
7 {
8 while ( p != L && p->data > q->data )
9 p = p->prior;
10 // 脱链结点p
11 q->prior->next = r;
12 r->prior = q->prior;
13 // 插入节点p
14 q->next = p->next;
15 q->prior = p;
16 p->next->prior = q;
17 p->next = q;
18 // 归位(相对位置)
19 q = r;
20 p = q->prior;
21 r = r->next;
22 }
23 }