基于array的序列和排序算法 学习笔记

有两种基本类型:
 
无序序列: 单位不按照特定顺序放置
有序序列: 单位按照字母顺序或者数字顺序放置

 

 

例子: 无序序列

 

我们直接来看删除操作

/*这里是重点.无序序列取出单位的方法很特别:首先遍历序列并找出所要取掉的单位,然后使用最后单位代替它,最后擦除最后单位。这个过程的程序效率用Big-O表示是N。*/

 
void List::Delete(/* in */ ItemType item)

// Precondition:

//     length > 0 && item is assigned

// Postcondition:

// If item is in data array

//     First occurrence of item is removed from the list; and

//     length is updated;

// else

//     no change to the list.

{

  int index = 0;

 

  // search for the item

  while (index < length && item != data[index])

       index++;

 

  if (index < length) {   // if the item is found

       data[index] = data[length-1]; // replace the item

       length–;

  }

}

 

 

下面是有序序列:

直接看重点insert和delete

 

Insert序列原理就是倒序地遍历序列,同时把单位右移空出一个位置。把插入的单位和空位前的单位比较,一旦发现插入单位大于空位前单位,立刻停止遍历把单位插入当前空位。

————————————————————

void SortedList::Insert(ItenType item)

{

     int  index;

 

     // find proper location for new element starting at bottom.

     index = length – 1;

     while (index>=0 && item<data[index])

     {

          data[index+1] = data[index]; // shift element down by one position

          index–;

     }

 

     data[index+1] = item;   // store the new item at the found location

     length++;               // increment the length of the list

}

    

————————————————————-

 

Delete操作:

算法概述:通过Binary search找出需要删除的单位,然后把此单位以后的所有单位左移一位,此单位自动被后一个单位覆盖。

————————————————————————-

void SortedList::Delete(ItemType item)

{

        int  position; //  a positive number – position of item, if found

                   // -1, if not found

     int  index;

 

     position = BinarySearch(item);

     if (position >= 0) {

          // shift up elements that follow deleted element in sorted list

          for (index=position; index<length; index++)

              data[index] = data[index+1];

 

          length–;

     }

}

————————————————————

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: