Osheep

时光不回头,当下最重要。

数据结构与算法(一)线性表

《数据结构与算法(一)线性表》

以上是几种线性表的实现以及定义,还没实现的以后会慢慢补充!

下面,根据已经实现的几个数据结构操作一波!

问题1

将顺序表的所有元素逆置,要求算法的空间复杂度为O(1)。

这个问题比较简单,借助一个变量,将前半部分和后半部分的元素交换即可。

void reverse(SqList *L) {
   ElemType temp;
   int i;
   for (i = 0; i < ListLength(*L) / 2; i++) {
       temp = L->elem[i];
       L->elem[i] = L->elem[L->length - i - 1];
       L->elem[L->length - i - 1] = temp;
   }
}
问题2

设计一个递归算法,删除不带头结点的单链表L中所有值为x的结点。

分析之后,我们不难写出如下代码:

void delX(LinkList *L, ElemType x)
{
    LinkList p;
    if (*L == NULL)
        return;
    if ((*L)->data == x)
    {
        p = *L;
        *L = p->next;
        free(p);
        delX(*L, x);
    }
    else
        delX((*L)->next, x);
}
问题3

已知一个已经从小到大排序的数组,这个数组中的一个平台(plateau)就是连续的一串值相同的元素,并且这一串元素不能再延伸。例如,在1,2,2,3,3,3,4,5,5,6中1,2.2,3.3.3,4,5.5,6都是平台。试编写一个程序,接收一个数组,把这个数组中最长的平台找出来。在上述的例子中3.3.3就是该数组中最长的平台。

编写时考虑以下几点:

使用的变量越少越好。
能否只把数组的元素每一个都只查一次就得到结果?
程序语句也要越少越好。
附上一精妙的很的参考答案:

int longest_plateau(int x[], int n)  
{  
     int  length = 1;         /* plateau length >= 1.     */  
     int  i;  
  
     for (i = 1; i < n; i++)  
          if (x[i] == x[i-length])  
               length++;  
     return length;  
}  

以上。

《数据结构与算法(一)线性表》

点赞